#1214. DWLABYR - Mê cung

Một mê cung gồm địa điểm đánh số từ tới và con đường đánh số từ tới . Con đường thứ cho phép đi từ địa điểm tới địa điểm theo một chiều, độ dài con đường là . Ban đầu cả địa điểm đều bị khóa. Khi một địa điểm bị khóa, nó sẽ không cho phép đi ra hay đi vào theo bất cứ con đường nào liên thuộc với nó. Ngược lại khi một địa điểm được mở khóa, người ta có thể thoái mái ra vào nó bằng bất kỳ con đường nào (tất nhiên vẫn phải đi theo chiều đã định của các con đường, không được đi ngược chiều).

Giáo sư được một nhà thám hiểm nhờ dùng máy tính mở khóa để thám hiểm mê cung. Hai người trao đổi qua các thông điệp thuộc một trong hai dạng:

• Giáo sư : Địa điểm vừa được mở khóa;
• Nhà thám hiểm : Bây giờ có thể đi từ tới hay không? Nếu đi được thì độ dài con đường ngắn nhất là bao nhiêu?

Yêu cầu: Biết được thông điệp và trình tự của chúng, hãy giúp giáo sư trả lời tất cả câu hỏi của nhà thám hiểm .

Dữ liệu vào:

• Dòng đầu chứa ba số nguyên dương ;
• dòng tiếp theo, dòng thứ chứa ba số nguyên dương ;
• dòng tiếp theo, mỗi dòng chứa một thông điệp, đầu dòng là ký tự cho biết đó là thông điệp của giáo sư hay nhà thám điểm . Nếu là thông điệp của giáo sư , tiếp theo là số nguyên cho biết địa điểm vừa được mở khóa. Nếu là thông điệp của nhà thám hiểm , tiếp theo là hai số nguyên ứng với câu hỏi hiện giờ có thể đi từ tới hay không?

Dữ liệu ra:

• Với mỗi câu hỏi của nhà thám hiểm , ghi ra trên một dòng độ dài đường đi ngắn nhất từ tới (nếu hiện tại chưa thể đi từ tới , in ra trên dòng số ).

Ví dụ:

Dữ liệu vào:

5 5 7
1 2 10
3 1 20
2 4 30
2 5 40
3 2 50
X 1
X 4
X 2
Y 1 4
X 3
Y 3 4
Y 5 3

Dữ liệu ra:

40
60
-1