Input

10
13 12
12 9
9 13
13 11
13 4
11 5
12 3
13 6
12 2
13 1
13 10
5 8
6 7
19
1
4
9
11
4
10
1
2
12
4
5
13
13
9
13
3
13
4
12
1 0
17
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
46 45
5 13
5 10
10 46
10 26
26 27
27 19
27 2
27 14
10 11
46 12
2 4
11 24
24 18
46 37
19 30
30 9
24 33
30 7
12 40
24 8
13 36
2 31
14 39
24 43
33 15
37 28
31 32
11 42
24 41
18 22
39 34
2 20
26 1
42 3
28 29
41 6
41 38
14 44
39 23
2 21
38 35
23 17
32 16
41 45
40 25
25
7
32
26
15
35
34
16
43
32
41
25
31
22
37
34
7
25
4
31
18
15
9
31
35
18
48 47
45 26
26 7
7 20
20 13
45 8
13 30
13 3
7 35
7 38
35 23
13 10
13 44
13 48
23 6
38 11
45 22
8 43
11 31
3 14
7 9
44 12
14 16
8 29
26 32
7 47
38 39
11 19
22 41
30 40
47 34
45 17
16 1
9 42
17 18
8 2
23 27
10 4
31 25
8 28
25 33
23 5
9 15
9 37
17 24
44 21
17 46
45 36
12
15
17
48
28
32
12
21
30
25
6
34
11
9 8
3 1
1 5
1 4
1 2
3 8
1 6
5 9
1 7
7
6
6
8
6
4
1
5
26 25
25 9
9 17
9 21
25 26
26 19
26 16
21 2
25 14
2 1
14 7
21 10
9 11
1 4
21 23
23 20
19 18
14 5
10 15
5 6
10 3
16 8
16 22
22 12
9 13
21 24
10
22
25
25
25
5
12
23
4
10
22
41 40
34 40
40 31
31 14
34 1
31 19
14 24
14 41
14 25
40 3
14 28
1 22
40 36
40 20
20 4
3 33
33 5
24 11
22 35
34 17
25 15
40 13
20 8
25 12
15 32
17 10
11 39
3 26
17 38
5 6
15 9
20 37
33 7
34 18
32 2
5 27
8 16
2 23
6 30
24 29
17 21
5
35
10
36
29
31
43 42
42 31
31 4
4 28
31 10
10 14
4 40
42 32
32 22
42 33
31 41
28 8
22 17
33 11
17 27
22 3
14 20
33 15
15 7
31 6
8 30
4 43
31 24
43 25
30 1
10 36
31 34
43 9
40 37
22 13
33 12
20 2
37 19
27 18
1 39
10 26
6 16
12 23
43 29
29 21
7 5
12 38
7 35
16
35
37
25
42
26
32
18
36
27
25
26
37
10
9
24
11
35 34
26 24
26 7
26 9
24 3
26 34
3 18
26 35
9 16
18 23
18 32
3 28
26 15
3 14
3 10
18 8
9 17
10 21
10 5
3 12
17 11
23 20
21 31
21 2
3 13
35 19
16 1
17 29
32 6
35 25
16 33
6 4
8 22
25 27
18 30
21
11
7
25
6
2
23
22
2
33
26
5
9
13
27
32
31
2
32
9
14
17
44 43
17 10
17 8
10 42
10 30
30 16
8 19
8 18
30 12
30 39
42 28
10 2
8 31
19 37
16 1
12 43
8 21
16 6
21 26
31 3
16 7
19 36
16 38
3 27
2 44
16 20
42 13
27 24
6 23
24 33
8 34
21 29
12 4
13 22
38 41
7 9
3 25
3 35
42 11
23 15
18 40
20 32
30 5
13 14
13
32
39
5
6
7
43
27
41
26
25
24
27
26