3
3
1 2
2 3
3 1
8
12
1 2
2 4
3 4
3 1
3 7
7 6
4 6
1 6
2 5
5 6
4 8
5 8
0