由于原网站样例文件缺失，本题没有样例数据，特向大家谢罪。

以下是我造的一组数据：

stdin:

7 6
1 2
2 3
3 4
4 5
5 6
6 7
6
1 1 
1 2 
1 3 
2 1 2
3 2 3 4
1 5

stdout:

6
5
4
11
12
2

（疯狂求饶）QwQ