Tree Merging

Bessie viết một trình hiển thị cây có gốc, trong đó mỗi nút mang một giá trị và các giá trị đôi một khác nhau. Trình hiển thị chỉ hỗ trợ duy nhất một thao tác: phép gộp.

Một phép gộp chọn hai nút khác nhau đang có cùng cha và thay chúng bằng một nút duy nhất. Nút mới mang giá trị bằng giá trị lớn hơn trong hai nút được chọn, và nhận tất cả các con của cả hai nút làm con của nó. Gốc của cây không bao giờ tham gia phép gộp (gốc không có cha).

Cho cây ban đầu gồm $N$ nút mang các giá trị $1,2,\dots ,N$ và cây cuối gồm $M$ nút, hãy tìm một dãy phép gộp biến cây ban đầu thành đúng cây cuối.

Dữ liệu vào

• Dòng đầu: số nguyên $T$, số test case.
• Với mỗi test case:
  • Dòng chứa $N$, số nút của cây ban đầu.
  • $N-1$ dòng, mỗi dòng hai số nguyên $a$ và $p$ cho biết nút $p$ là cha của nút $a$ trong cây ban đầu. Nút duy nhất không xuất hiện ở vị trí $a$ chính là gốc.
  • Dòng chứa $M$, số nút của cây cuối.
  • $M-1$ dòng, mỗi dòng hai số nguyên $a$ và $p$ cho biết nút $p$ là cha của nút $a$ trong cây cuối.

Giá trị các nút của cây cuối là một tập con của $\{1,2,\dots ,N\}$, và gốc của cây cuối trùng với gốc của cây ban đầu.

Dữ liệu ra

Với mỗi test case, in ra:

• Dòng đầu: số phép gộp $K$.
• $K$ dòng tiếp theo, mỗi dòng hai số $x$ và $y$: gộp hai nút đang mang giá trị $x$ và $y$. Tại thời điểm thực hiện, hai nút này phải khác nhau, còn tồn tại và có cùng cha. Nút thu được mang giá trị $max(x,y)$.

Mỗi phép gộp làm số nút giảm đúng $1$, nên luôn có $K=N-M$. Có thể có nhiều dãy phép gộp hợp lệ, in ra dãy nào cũng được.

Ràng buộc

• $1\le M\le N$
• Tổng $N$ của tất cả test case trong một file dữ liệu không vượt quá $1000$
• Dữ liệu đảm bảo luôn tồn tại ít nhất một dãy phép gộp hợp lệ

Ví dụ