9 3
10 5 6 4 3 2 3 1 4
1 2
1 3
2 4
2 5
4 6
4 7
3 8
3 9
73 2 5 6
34 1 3
1000000000 2 7 8