Cây thần thánh

Cho số nguyên $n$. Bạn cần xây dựng một cây gồm $n$ đỉnh (cây là đồ thị vô hướng liên thông có $n$ đỉnh và $n-1$ cạnh, giữa hai đỉnh bất kỳ có đúng một đường đi đơn).

Cây phải thỏa mãn $m$ ràng buộc. Mỗi ràng buộc gồm ba số nguyên đôi một phân biệt $a$, $b$, $c$, nghĩa là: đỉnh $b$ không được nằm trên đường đi đơn giữa đỉnh $a$ và đỉnh $c$.

Bảo đảm với mọi bộ ràng buộc trong giới hạn của đề, luôn tồn tại một cây hợp lệ. Nếu có nhiều cây hợp lệ, bạn chỉ cần in ra một cây bất kỳ.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ là số bộ dữ liệu.
• Với mỗi bộ dữ liệu:
  • Dòng đầu chứa hai số nguyên $n$ và $m$.
  • $m$ dòng tiếp theo, mỗi dòng chứa ba số nguyên phân biệt $a_i$, $b_i$, $c_i$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra $n-1$ dòng mô tả $n-1$ cạnh của cây. Mỗi dòng chứa hai số nguyên $u$ và $v$ ($1\le u,v\le n$, $u\ne v$) cho biết có một cạnh nối đỉnh $u$ và đỉnh $v$. Các cạnh in ra phải tạo thành một cây thỏa mãn mọi ràng buộc.

Ràng buộc

• $1\le t\le {10}^4$
• $3\le n\le {10}^5$
• $1\le m<n$
• $1\le a_i,b_i,c_i\le n$; $a_i,b_i,c_i$ đôi một phân biệt.
• Tổng $n$ trên tất cả các bộ dữ liệu không vượt quá ${10}^5$.

Ví dụ