Vừa hoàn thành xong khoá học về lý thuyết đồ thị, cô bò Bessie đã bắt đầu muốn code một chương trình mô phỏng đồ thị. Hiện tại, do kinh nghiệm còn thiếu, chương trình của cô chỉ có thể mô phỏng được cây có gốc với các node có giá trị khác nhau, đồng thời chương trình mới chỉ có một chức năng duy nhất: ghép cây.

Về cơ bản, ghép cây là chức năng lấy \(2\) node khác nhau có cùng cha trên cây và hợp lại thành \(1\) node duy nhất, giá trị của node mới này là giá trị lớn hơn trong \(2\) giá trị của node cũ, các node con sẽ là hợp các node con của \(2\) node này (nếu có).

Không may là sau khi Bessie thực hiện một số lần ghép cây, chương trình của cô nàng bị văng (crashed), mất đi lịch sử của tất cả các lần ghép mà cô nàng thực hiện. Tất cả những gì Bessie nhớ là cây lúc ban đầu và cây sau khi cô thực hiện các lần ghép.

Bạn được cho \(2\) cái cây này, hãy tìm \(1\) dãy các lần ghép của cô nàng. Dữ liệu đảm bảo dãy này tồn tại.

Input sẽ gồm \(T\) \((1 \le T \le 100)\) bộ test khác nhau. Tổng số node của tất cả các test không quá \(1000\).

Input

• Dòng đầu là số \(T\).
• Dòng thứ hai là số lượng node \(N\) \((2 \le N \le 1000)\) trên cây ban đầu, với các giá trị trên node được đánh số từ \(1\) đến \(N\).
• \(N - 1\) dòng tiếp theo gồm hai số \(v_i\) và \(p_i\) \((1 \le v_i, p_i \le N)\) với ý nghĩa node mang giá trị \(v_i\) là con của node mang giá trị \(p_i\) trong cây ban đầu.
• Dòng tiếp theo là số lượng node \(M\) \((2 \le M \le N)\) của cây sau khi Bessie ghép cây.
• \(M - 1\) dòng tiếp theo gồm hai số \(v_i\) và \(p_i\) \((1 \le v_i, p_i \le N)\) với ý nghĩa node mang giá trị \(v_i\) là con của node mang giá trị \(p_i\) sau khi Bessie ghép cây.

Output

• Với mỗi test, in ra số lần thực hiện ghép cây, theo sau đó là dãy gồm các cặp số \((a_i, b_i)\) là giá trị của \(2\) node được ghép ở lần thứ \(i\), mỗi cặp được in ra trên \(1\) dòng.
• Nếu có nhiều phương án, in ra bất kì.

Scoring

• Subtask \(1\): Số lượng lá (node không có node con) ở cả \(2\) cây là như nhau.
• Subtask \(2\): Không có ràng buộc gì thêm.

1
8
7 5
2 1
4 2
5 1
3 2
8 5
6 2
4
8 5
5 1
6 5

4
2 5
4 8
3 8
7 8