10 5
1 2
2 3
2 4
4 5
5 6
3 7
7 8
5 9
6 10
8 10 2
9 2 1
7 8 4
5 6 3
5 4 5