Inputs: 9

1 2
3 4
5 6
7 8

0 1
2 4
5 7
6 8

0 3
1 2
4 8
6 7

0 5
1 6
2 4
3 7

2 6
3 5
4 7

1 3
2 5
4 6
7 8

2 3
4 5