DWITE Contest

Test Case for Question #5 in DWITE 2007-2008 High School Round 2

Contest: DWITE 2007-2008 High School Round 2
Question: #5
Input File: DATA5.txt
Output File: OUT5.txt


Input

2
1
1 2
5
5
1 2
2 3
3 1
3 4
5 4
7
10
7 1
7 2
7 3
7 4
7 5
7 6
3 4
4 6
6 5
5 3
7
6
1 2
1 3
2 4
2 5
3 6
3 7
5
5
1 2
3 4
5 1
2 3
4 5




Output

1
2
2
6
0