Tree of Life (hard)

Description:

Input:

The input format is the same as in the medium version, except that now the bound on n is 2 ≤ n ≤ 1000 and that k = 2.

Output:

The same as in the medium version.

Sample Input:

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

Sample Output:

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