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