DWITE Contest

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

Contest: DWITE 2009-2010 High School Round 2
Question: #2
Input File: DATA2.txt
Output File: OUT2.txt


Input

1 2
2 3
3 4
4 5
5 6
3
5
7
10
11
1 1
1 1
1 1
1 1
1 1
1
2
3
4
5
1 1
1 1
1 1
1 1
1 1
42
42
42
42
42
1 1
1 1
1 1
1 1
1 1
2
2
2
2
2
0 0
0 1
1 0
1 1
2 0
0
1
1
0
0




Output

4
1
0
5
2