5 11
1 1 2 1
2 1 3
1 2 3 1
3 2
2 1 2
1 2 4 2
1 2 5 2
3 3
2 4 5
2 1 4
4