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