DWITE Contest

Test Case for Question #5 in DWITE 2009-2010 High School Round 3

Contest: DWITE 2009-2010 High School Round 3
Question: #5
Input File: DATA5.txt
Output File: OUT5.txt


Input

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




Output

2
3
0
4
3