6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1