Chiếc bánh bị cắt

Một chiếc bánh có hình dạng đa giác lồi $n$ đỉnh. Các đỉnh của nó được đánh số bởi $n$ số nguyên phân biệt từ $1$ đến $n$, nhưng thứ tự đánh số là hoàn toàn tùy ý: đi vòng quanh đa giác, các số hiệu không nhất thiết tăng dần.

Chiếc bánh được cắt thành $n-2$ miếng tam giác theo quy tắc sau. Mỗi lần cắt, ta chọn ba đỉnh liên tiếp của đa giác hiện tại và cắt rời tam giác tạo bởi ba đỉnh đó ra khỏi bánh; phần bánh còn lại vẫn phải là một đa giác lồi. Sau đúng $n-2$ lần cắt như vậy, chiếc bánh được chia hết thành các miếng tam giác.

Bạn nhận được $n-2$ miếng tam giác theo thứ tự ngẫu nhiên. Mỗi miếng được mô tả bởi số hiệu ba đỉnh của nó, cũng theo thứ tự ngẫu nhiên. Nhiệm vụ của bạn là khôi phục lại:

• một hoán vị $p_1,p_2,\dots ,p_n$ của $1,2,\dots ,n$ — số hiệu các đỉnh của đa giác khi đi vòng quanh nó (theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ đều được);
• một hoán vị $q_1,q_2,\dots ,q_{n-2}$ của $1,2,\dots ,n-2$ — thứ tự cắt các miếng, trong đó $q_i$ là số hiệu của miếng được cắt ở lần thứ $i$ (miếng được đánh số theo thứ tự xuất hiện trong dữ liệu vào).

sao cho nếu đa giác có thứ tự đỉnh là $p$ thì việc cắt lần lượt các miếng $q_1,q_2,\dots ,q_{n-2}$ luôn hợp lệ: mỗi lần cắt tách ra đúng một miếng tam giác và phần còn lại luôn là một đa giác lồi.

Dữ liệu đảm bảo luôn tồn tại đáp án. Nếu có nhiều đáp án, in ra một đáp án bất kì.

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên $t$ — số bộ dữ liệu.
• Với mỗi bộ dữ liệu:
  • Dòng đầu chứa một số nguyên $n$ — số đỉnh của chiếc bánh.
  • $n-2$ dòng tiếp theo, dòng thứ $i$ chứa ba số nguyên đôi một khác nhau $a,b,c$ — số hiệu ba đỉnh của miếng thứ $i$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra hai dòng:

• Dòng thứ nhất chứa $n$ số nguyên phân biệt $p_1,p_2,\dots ,p_n$.
• Dòng thứ hai chứa $n-2$ số nguyên phân biệt $q_1,q_2,\dots ,q_{n-2}$.

Ràng buộc

• $1\le t\le 1000$
• $3\le n\le {10}^5$
• $1\le a,b,c\le n$
• Tổng $n$ trên tất cả các bộ dữ liệu không vượt quá ${10}^5$

Ví dụ