Input 
2
5
1 2
1 3
2 4
2 5
6
1 2
1 3
1 4
2 5
2 6
Output 
1 2
1 2
1 3
2 3