input:

5 8 2
1 2
2 4
3 4
1 3
1 5
2 5
3 5
4 5
1 6
3 3 0
6 7
7 8
8 6
5 10
3 2 2
10 11
10 12
11 13
2 1 0
13 9
11 14
3 2 0
14 15
14 16
5 8 2
1 2
2 4
3 4
1 3
1 5
2 5
3 5
4 5
2 7
3 3 0
7 9
7 8
8 9
3 11
3 2 0
11 12
11 13
5 4 2
2 1
3 2
4 1
5 4
4 8
5 4 0
7 6
8 6
9 6
10 9
5 15
5 4 0
12 11
13 11
14 12
15 12
5 4 2
2 1...

output:

8
6
7
7
7
8
7
9
10
10
11
8
10
10
8
11
12
12
13
15
12
11
12
12
13
13
15
15
17
13
12
15
16
17
16
19
18
20
8
8
9
9
9
10
11
12
12
10
10
12
13
14
15
15
16
16
14
13
15
15
15
19
19
20
21
15
15
18
16
22
22
23
24
25
9
12
10
12
10
13
12
14
15
10
11
14
15
17
17
19
19
20
15
16
19
20
20
21
23
25
24
20
20
21
18
2...

result:

ok 476 lines