in：

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

out：

1
0