Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

DS2509 - Cấu trúc dữ liệu Disjoint Sets

Disjoint-set hiểu 1 cách đơn giản là 1 cách lưu trữ các tập hợp phần tử của 1 tập lớn cho trước.

Các phép toán thường được quan tâm tới trong disjoint-set là:

MakeSet(i): tạo ra 1 tập chỉ có i.

FindSet(i): tìm tập hợp mà nút i thuộc.

Union(i,j): ghép 2 tập hợp chứa i và j với nhau.

Xét bài toán:

Cho 1 đồ thị gồm N đỉnh được đánh số từ 1 đến N, giữa 2 đỉnh bất kỳ đều có thể nối hoặc không nối với nhau. Ở trạng thái ban đầu tất cả các đỉnh đều không có cạnh nối.

Bạn được cho một số yêu cầu, trong đó mỗi yêu cầu có 2 dạng:

Union(x, y): X Y 1 có ý nghĩa là bạn cần nối 2 đỉnh X và Y.

Find(x, y): X Y 2 có ý nghĩa là bạn cần cho biết với trạng thái như hiện tại thì 2 đỉnh X và Y có thuộc cùng một thành phần liên thông hay không? Hai đỉnh được coi là thuộc cùng một thành phần liên thông nếu có đường đi từ đỉnh này đến đỉnh kia qua 1 số đỉnh khác và 2 đỉnh liên tiếp trên đường đi đều có cạnh nối.

Input

Dòng đầu tiên ghi một số nguyên dương P là số yêu cầu.

Trong P dòng tiếp theo, mỗi dòng ghi ba số nguyên dương X, Y, Z với ý nghĩa có yêu cầu loại Z với 2 đỉnh X và Y.

Output

Với mỗi yêu cầu dạng X Y 2 (với Z = 2) bạn cần ghi ra số 0 hoặc 1 trên 1 dòng tùy thuộc 2 đỉnh X và Y không thuộc hoặc thuộc cùng một thành phần liên thông.

Example

Input:
9
1 2 2
1 2 1
3 7 2
2 3 1
1 3 2
2 4 2
1 4 1
3 4 2
1 7 2

Output:
0
0
1
0
1
0

Giới hạn:
1 ≤ N ≤ 10000
1 ≤ P ≤ 50000


Được gửi lên bởi:special_one
Ngày:2009-01-04
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:C CSHARP CPP JAVA PAS-FPC

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.