входные данные
9 8 1
1 2
1 3
1 4
4 5
5 6
6 7
7 8
8 9
выходные данные
4
входные данные
16 16 3
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 5
1 15
15 16
выходные данные
2
входные данные
6 5 1
1 2
2 3
3 4
4 5
4 6
выходные данные
2
входные данные
5 6 1
3 1
3 2
3 4
3 5
1 2
4 5
выходные данные
1
входные данные
7 7 2
1 2
2 3
3 4
4 1
1 5
5 6
6 7
выходные данные
2