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

Case #1: 7
Case #2: 8
Case #3: 1
Case #4: 0