Tổ đội

Trong một dự án trồng cây xanh, FullHouse Dev được giao nhiệm vụ tổ chức các em nhỏ thành những đội nhóm để chăm sóc vườn ươm. Mỗi em đều có một chỉ số sức mạnh riêng, và việc phân chia nhóm cần được thực hiện một cách khoa học và hiệu quả.

Bài toán

Ban đầu có \(n\) em nhỏ, mỗi em có một chỉ số sức mạnh riêng. Lúc đầu, mỗi em tạo thành một nhóm riêng, vì vậy có \(n\) nhóm. FullHouse Dev cần thực hiện \(q\) thao tác để giúp tổ chức các em thành những đội nhóm hiệu quả.

Có 3 loại thao tác:

• Loại 1: Gộp nhóm của em \(A\) với nhóm của em \(B\)
• Loại 2: In ra kích thước và tổng sức mạnh của nhóm mà em \(A\) đang thuộc về
• Loại 3: Chuyển em \(A\) sang nhóm của em \(B\)

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(T\) - số lượng test case
• Dòng đầu của mỗi test case chứa hai số nguyên \(n\) và \(q\)
• \(q\) dòng tiếp theo, mỗi dòng mô tả một thao tác theo một trong ba loại trên

OUTPUT FORMAT:

• Với mỗi test case, in ra một mảng chứa kết quả của tất cả các thao tác loại 2

Ràng buộc:

• \(1 \leq T \leq 10^4\)
• \(1 \leq n, q \leq 10^5\)
• Với thao tác loại 1 hoặc 3: \(1 \leq A, B \leq n\)
• Với thao tác loại 2: \(1 \leq A \leq n\)

Ví dụ

INPUT

2
4 3
1 1 2
3 2 3
2 3
3 2
2 1
2 2

OUTPUT

2 5
1 1
1 2

Giải thích

Test case 1:

• Ban đầu có 4 em, thực hiện các thao tác:
• Thao tác 1: Gộp nhóm của em 1 và 2, tạo thành cấu hình {1, 2}, {3}, {4}
• Thao tác 2: Chuyển em 2 sang nhóm của em 3, tạo thành {1}, {2, 3}, {4}
• Thao tác 3: Kiểm tra nhóm của em 3, có 2 thành viên với tổng sức mạnh là 5 Do đó kết quả là [2, 5]

Test case 2:

• Ban đầu có 3 em với cấu hình {1}, {2}, {3}
• Thao tác 1: Kiểm tra nhóm của em 1, có 1 thành viên với sức mạnh là 1
• Thao tác 2: Kiểm tra nhóm của em 2, có 1 thành viên với sức mạnh là 2

Contributers: