IN:
26 31
1 2
2 3
1 3
2 7
7 26
7 4
7 15
26 19
19 20
19 21
20 21
10 9
10 11
9 11
11 8
8 12
12 14
12 13
13 14
23 25
24 25
23 24
22 23
6 22
6 5
6 4
4 5
15 16
16 17
16 18
18 17

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


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

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

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

3 1
1 3

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

4 4
1 2
1 4
1 3
2 3

12 9
1 7
2 6
4 9
9 10
8 12
1 5
1 8
8 11
4 10

4 2
1 2
2 3

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

6 4
1 2
1 3
3 4
6 5

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

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

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

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

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

5 4
1 2
2 3
3 5
1 4

10 7
1 2
2 3
3 5
3 6
3 10
3 4
7 8

-1 -1

OUT:
3
1
1
1
1
2
0
1
4
2
2
2
4
3
2
2
5
1
5