input:

7 2
1 4
2 1
4 3
3 4
4 4
4 3
2 1
1 2
2 3
1 4
4 5
5 6
2 7
CC 4 4
QS 5 1

answer:

8

https://www.luogu.com.cn/blog/Link-Cut-Y/p3313-sdoi2014-lv-xing-ti-xie