in:

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

out:

4
4
3