QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#882640#8704. 排队MaMengQi100 ✓515ms60440kbC++113.6kb2025-02-05 10:14:072025-02-05 10:14:07

詳細信息

Subtask #1:

score: 4
Accepted

Test #1:

score: 4
Accepted
time: 3ms
memory: 44912kb

input:

0 8
1 0
1 1
1 2
3 2
2 2 0
3 1
3 2
3 3

output:

2
3
1
2

result:

ok 4 lines

Test #2:

score: 4
Accepted
time: 2ms
memory: 44864kb

input:

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

output:

1
1
3
3
3
3
2
2
4
3
6
2
14
2
12
14
17
12
5
12
18
15
13
7
23
29
19
13
22
13
19
36
4
15
38
35
30
31
43
2
32
11
53
15
40
3
36
39
16
25
30
24
7
10
14
38
12
38
40
35
10
19
30
15
31
8
15
69
2
24
3
30
44
57
57
38
41
37
40
50
40
17
65
83
49
56
74
17
40
82
39
71
92
26
37
76
8
34
14
63
37
43
13
46
37
92
19
69...

result:

ok 153 lines

Test #3:

score: 4
Accepted
time: 5ms
memory: 43988kb

input:

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

output:

1
1
1
1
1
1
1
3
3
4
6
11
4
1
8
16
6
7
19
7
7
5
28
10
28
22
9
31
3
21
23
31
26
9
30
5
39
40
45
48
1
28
54
47
4
48
37
50
26
5
22
41
12
1
63
46
32
62
43
28
45
23
37
1
13
20
64
10
48
7
41
13
10
54
16
10
66
7
65
1
76
35
74
14
56
16
28
68
76
10
80
12
4
25
4
13
44
69
76
4
21
15
4
49
90
39
87
42
90
73
43
94...

result:

ok 159 lines

Test #4:

score: 4
Accepted
time: 4ms
memory: 43580kb

input:

0 473
1 0
3 1
2 1 0
3 1
2 1 0
1 0
1 1
1 1
2 1 0
3 4
1 3
1 1
1 2
3 4
1 6
2 6 1
3 2
1 1
2 4 0
3 6
2 8 5
2 6 2
2 3 0
2 7 2
1 3
2 4 2
3 3
3 3
2 1 0
2 3 2
1 6
1 6
3 7
3 1
2 2 0
3 4
3 6
1 2
3 5
3 8
1 9
2 4 2
1 5
1 6
2 3 0
3 16
1 4
2 8 3
3 15
3 6
3 1
1 7
3 11
1 6
1 10
1 20
3 10
1 20
1 22
3 19
3 8
1 11
3 2
...

output:

1
1
3
5
1
6
1
1
2
11
6
3
10
11
10
5
9
15
13
2
15
7
10
6
29
17
10
26
6
3
30
18
31
11
17
7
22
24
17
30
19
26
14
40
43
6
14
37
43
46
9
44
45
12
7
24
23
18
10
39
56
3
50
18
1
50
69
69
37
44
20
30
2
17
41
61
60
39
25
27
66
8
16
81
43
54
10
79
59
56
63
10
11
26
75
42
10
46
6
12
77
69
36
6
99
67
79
1
83
47...

result:

ok 145 lines

Subtask #2:

score: 19
Accepted

Test #5:

score: 19
Accepted
time: 230ms
memory: 52416kb

input:

1 298913
1 0
3 1
3 1
3 1
3 1
3 1
1 0
1 0
3 3
1 2
1 2
3 5
3 5
1 1
1 3
1 4
3 3
1 3
1 6
3 7
3 2
3 5
3 8
3 2
1 8
3 3
1 4
3 2
3 7
1 3
3 4
1 10
3 14
3 13
1 12
3 4
1 8
1 15
1 16
3 9
3 14
3 10
3 8
3 7
1 16
1 15
3 16
3 13
1 19
3 13
3 1
3 14
1 18
1 22
3 8
1 17
3 18
3 9
1 18
3 9
3 1
1 20
3 11
3 5
3 2
3 22
1 22...

output:

1
1
1
1
1
1
3
3
1
3
4
5
7
4
1
4
3
7
14
2
7
3
18
17
11
4
13
2
2
18
21
12
17
3
3
22
22
6
5
20
5
17
22
27
18
23
31
4
1
19
21
12
22
34
33
5
22
40
40
8
14
42
35
9
40
24
18
13
36
8
25
49
32
34
47
14
47
19
38
10
14
31
40
17
20
45
46
1
35
1
43
9
47
33
56
2
8
19
41
21
18
50
22
61
27
2
2
6
4
58
62
35
61
59
10...

result:

ok 179182 lines

Test #6:

score: 19
Accepted
time: 243ms
memory: 58112kb

input:

1 296745
1 0
3 1
3 1
1 0
1 0
3 2
1 0
3 4
1 4
1 0
1 4
3 5
1 0
1 0
1 0
1 0
1 8
1 4
1 0
1 0
1 8
3 9
1 0
1 8
1 4
1 0
1 0
1 0
1 0
3 3
1 0
1 7
1 0
1 0
1 7
1 9
1 3
3 15
1 0
1 3
1 10
3 16
1 0
1 0
1 0
3 10
1 10
1 0
1 0
3 11
1 0
1 0
3 29
1 0
3 26
3 16
1 0
1 0
1 0
1 0
1 0
1 1
1 0
1 5
1 1
3 21
3 36
3 42
3 23
3 ...

output:

1
1
2
1
4
5
21
9
19
16
17
24
11
28
21
12
7
19
19
55
37
55
24
47
1
62
37
44
39
59
30
85
48
5
8
46
61
74
39
34
67
12
58
1
107
83
87
60
12
93
119
81
37
51
112
25
125
55
98
94
9
71
46
33
121
64
4
128
144
128
100
10
133
25
170
107
179
19
19
9
2
144
192
110
28
172
115
101
162
108
48
83
6
169
171
18
194
40...

result:

ok 98880 lines

Test #7:

score: 19
Accepted
time: 261ms
memory: 53704kb

input:

1 297653
1 0
3 1
1 1
3 2
1 2
3 1
1 0
1 1
3 1
3 3
1 2
3 4
1 2
3 2
3 1
1 0
3 6
3 8
1 5
3 6
1 6
3 4
1 2
1 5
3 9
3 3
1 9
3 4
1 6
3 6
3 5
1 4
1 8
3 2
3 5
1 1
3 17
3 12
1 7
1 10
1 0
1 8
1 10
3 21
3 12
3 2
1 5
1 8
3 12
3 8
1 4
3 24
3 2
3 1
3 3
1 6
1 8
1 8
3 4
1 0
3 5
3 27
1 2
3 22
1 8
1 10
1 1
1 8
1 5
1 3
...

output:

1
2
1
2
5
1
4
2
7
1
8
2
6
12
2
11
4
10
6
6
8
3
10
13
12
2
3
16
9
25
8
14
5
28
8
16
30
11
1
11
28
22
41
7
5
32
52
7
25
24
48
46
31
41
43
52
41
27
22
48
63
39
2
56
69
11
78
8
47
35
70
43
47
50
30
86
85
17
42
7
91
51
44
30
47
29
59
90
43
92
85
98
55
23
43
106
76
39
26
109
110
40
10
110
73
108
67
42
107...

result:

ok 148504 lines

Test #8:

score: 19
Accepted
time: 216ms
memory: 52900kb

input:

1 292283
1 0
1 0
3 2
1 0
1 0
3 3
3 4
1 2
3 1
3 1
3 4
1 0
1 5
1 7
3 3
1 0
3 9
3 7
1 0
3 5
1 0
3 10
3 10
3 4
1 9
3 11
3 1
1 0
1 2
3 4
1 10
3 10
3 10
1 0
3 14
3 12
3 16
3 6
1 0
3 15
1 0
3 5
3 1
3 14
3 3
3 5
3 1
3 13
3 3
1 0
3 8
1 0
3 20
3 12
1 0
1 7
1 0
3 11
1 4
3 10
3 11
3 2
3 17
1 0
1 0
1 0
3 23
3 18...

output:

1
2
1
5
5
1
3
1
7
7
2
2
5
1
12
7
3
3
12
7
1
8
6
15
18
14
12
15
18
4
12
18
1
11
9
10
9
18
6
4
8
3
4
8
29
3
14
34
4
18
22
22
32
17
36
1
24
8
11
17
24
8
38
26
17
16
36
14
49
38
7
19
29
19
19
4
29
36
21
46
2
5
50
12
54
47
22
15
13
63
13
63
19
39
56
72
66
35
44
57
11
21
52
11
73
43
23
16
17
24
58
47
26
4...

result:

ok 167157 lines

Test #9:

score: 19
Accepted
time: 262ms
memory: 54184kb

input:

1 291033
1 0
1 1
3 1
3 1
1 2
1 0
3 4
3 3
3 1
3 3
3 2
1 1
1 5
3 5
3 2
1 1
1 5
1 5
3 7
3 1
3 8
3 3
3 8
1 2
3 5
1 6
3 11
3 1
1 9
3 8
3 6
1 4
3 1
3 8
1 10
3 1
1 2
1 5
3 7
3 15
1 1
3 7
3 12
1 6
1 5
1 0
1 3
3 20
3 1
3 12
1 9
3 18
3 17
1 5
3 5
1 5
1 7
3 19
1 1
3 3
3 3
1 1
3 26
1 4
1 7
1 7
1 5
3 26
3 18
1 0...

output:

1
1
1
4
2
4
3
3
5
3
2
6
9
6
4
8
2
7
8
3
8
3
4
13
5
9
1
4
11
15
5
7
11
25
25
6
7
24
36
3
31
31
43
3
49
20
39
29
9
47
12
55
3
38
34
14
57
7
15
50
60
24
55
8
25
34
34
7
21
62
72
69
19
14
26
70
20
37
35
14
77
71
80
13
56
2
9
20
28
63
82
14
75
69
26
101
84
70
75
30
37
49
42
65
54
41
110
107
86
69
2
34
10...

result:

ok 145645 lines

Test #10:

score: 19
Accepted
time: 225ms
memory: 54156kb

input:

1 296808
1 0
3 1
1 0
1 0
1 0
3 3
1 3
1 0
3 3
1 0
3 5
3 5
3 2
3 1
3 3
1 0
1 0
1 6
1 9
3 6
1 0
1 6
3 12
1 0
1 2
1 0
3 13
3 1
1 0
3 13
1 8
1 2
3 18
1 0
1 10
1 0
1 0
3 22
3 21
3 10
1 0
1 0
1 3
3 8
3 26
3 5
1 0
3 11
1 0
3 4
3 9
3 19
1 0
3 15
3 29
1 10
1 0
3 18
3 8
1 0
1 4
1 0
3 34
1 0
1 0
1 4
3 20
1 3
1 ...

output:

1
2
3
5
5
6
7
4
5
1
9
16
10
8
2
16
15
12
21
22
12
21
12
26
28
1
17
16
1
13
16
33
14
26
26
34
4
41
44
46
33
9
37
24
22
39
37
48
20
25
17
31
55
69
52
16
5
54
40
46
49
12
23
69
15
29
37
81
4
26
9
5
61
89
75
24
4
17
5
25
63
75
57
96
21
75
105
35
83
93
55
59
31
35
54
109
103
83
68
59
2
47
122
5
95
57
116...

result:

ok 148730 lines

Test #11:

score: 19
Accepted
time: 186ms
memory: 48468kb

input:

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

output:

4
2
5
1
1
3
2
5
1
7
4
2
1
4
9
11
4
4
1
1
6
10
10
11
7
11
6
11
17
6
5
1
16
11
2
6
3
10
4
4
6
8
9
3
6
2
7
18
6
13
5
19
2
5
15
1
23
18
7
5
7
2
5
1
26
14
15
19
4
24
15
1
5
15
6
14
21
22
2
26
24
27
1
8
16
29
29
22
8
8
18
7
19
30
9
27
9
22
16
26
33
11
16
1
28
21
29
19
31
21
11
30
36
20
23
25
28
28
27
32
3...

result:

ok 234925 lines

Test #12:

score: 19
Accepted
time: 242ms
memory: 55580kb

input:

1 296974
1 0
1 0
1 1
1 1
1 4
3 2
1 1
3 6
1 6
1 3
3 5
3 8
3 8
1 5
3 9
1 7
3 1
3 3
1 8
3 9
1 11
1 12
1 12
1 6
1 6
1 10
1 13
3 15
1 14
1 17
1 20
3 21
3 1
1 13
1 18
3 9
3 18
3 16
1 22
3 22
3 4
1 24
1 20
1 18
3 26
1 25
3 12
3 3
3 19
3 28
1 26
3 13
3 14
1 26
1 29
3 26
3 13
1 26
1 32
3 32
1 25
1 25
3 27
1 ...

output:

1
3
6
8
8
7
2
9
8
5
10
2
13
22
4
21
11
10
18
15
20
25
22
20
10
24
11
34
19
29
21
13
26
15
20
48
28
48
5
18
49
24
16
22
16
75
53
71
13
27
11
41
73
36
47
52
62
84
18
61
83
82
4
49
84
8
81
67
91
26
44
41
2
61
77
89
74
79
30
69
63
60
96
61
79
11
79
79
100
68
4
42
11
51
44
85
12
92
81
99
12
40
106
36
31
...

result:

ok 126807 lines

Test #13:

score: 19
Accepted
time: 224ms
memory: 56732kb

input:

1 293712
1 0
3 1
1 1
1 0
3 1
1 0
1 0
1 0
1 0
1 0
3 5
3 3
3 2
1 7
1 0
1 7
3 4
1 6
3 7
3 10
3 5
1 4
1 0
3 3
3 7
3 6
1 9
3 12
3 12
3 12
3 15
3 6
1 0
1 0
1 0
1 4
3 6
3 6
1 0
1 3
1 0
3 16
3 5
1 6
3 9
3 22
3 4
1 0
3 17
1 2
1 7
1 0
1 0
3 12
3 28
1 2
1 4
3 15
1 4
3 5
3 13
3 27
3 3
3 6
1 0
3 27
3 21
1 5
3 8
...

output:

1
2
4
6
8
8
3
1
8
12
4
7
9
9
9
7
8
11
11
5
15
11
1
17
5
19
1
16
20
25
2
26
17
3
28
12
11
9
13
28
3
2
6
9
16
11
23
32
28
9
2
21
4
46
17
32
18
4
42
55
41
37
21
19
43
38
10
3
25
16
38
16
50
62
24
70
32
63
83
79
42
7
81
26
72
58
16
85
93
14
33
44
87
64
15
52
84
63
34
16
82
121
59
85
65
22
74
44
81
10
23...

result:

ok 126007 lines

Test #14:

score: 19
Accepted
time: 235ms
memory: 56988kb

input:

1 292001
1 0
3 1
3 1
1 0
3 2
3 2
1 2
1 1
3 1
1 4
3 4
1 0
3 2
1 1
3 2
1 4
3 5
1 5
3 6
1 3
1 9
1 0
1 3
3 1
3 2
1 0
1 0
1 2
3 13
3 1
1 0
3 15
1 0
1 3
3 6
1 0
3 9
1 4
1 0
3 10
1 0
1 7
1 0
3 3
1 6
1 0
1 0
1 0
1 4
1 0
1 0
3 2
1 1
1 2
3 17
1 4
3 13
1 5
1 0
1 0
1 0
3 22
1 0
3 35
1 6
1 0
3 15
1 0
1 0
3 23
3 ...

output:

1
1
1
1
3
4
2
2
8
1
7
3
8
10
2
6
19
14
13
17
11
22
11
33
17
14
42
8
24
47
40
62
21
34
29
71
41
6
42
38
3
62
5
41
45
12
16
54
22
43
84
84
53
14
69
34
57
18
82
32
86
17
73
50
38
43
32
79
11
57
44
65
44
108
53
22
103
90
60
41
108
122
17
73
144
136
176
108
18
30
66
191
181
87
14
195
135
67
107
154
23
12...

result:

ok 97400 lines

Test #15:

score: 19
Accepted
time: 246ms
memory: 57604kb

input:

1 295477
1 0
3 1
1 0
3 1
1 2
1 3
1 1
3 2
1 3
1 5
3 4
3 2
3 2
1 1
1 1
1 2
1 4
1 10
3 9
3 11
1 7
3 13
1 13
1 12
1 6
1 16
1 8
1 11
1 10
3 14
3 9
3 7
1 12
1 16
1 19
1 17
1 24
3 8
3 12
1 21
3 25
1 21
1 25
1 24
3 9
1 28
3 21
3 12
1 25
1 26
3 21
1 25
3 22
3 16
1 28
3 30
3 11
3 13
1 34
3 23
1 29
3 24
3 27
1...

output:

1
2
1
4
1
1
9
7
13
20
14
18
20
4
14
23
5
4
5
13
12
22
24
33
27
15
6
36
39
22
6
7
13
16
28
43
2
21
7
41
33
24
20
30
49
26
57
50
43
48
59
15
33
67
53
56
42
50
23
13
69
46
64
58
67
24
44
70
32
64
15
51
21
7
89
87
40
78
95
90
34
64
17
102
24
122
45
94
15
107
133
36
131
107
65
5
57
12
69
115
153
152
40
5...

result:

ok 117628 lines

Test #16:

score: 19
Accepted
time: 211ms
memory: 52532kb

input:

1 291841
1 0
1 1
3 2
1 0
3 3
1 3
3 1
3 3
3 3
1 2
3 4
3 1
3 4
1 1
3 3
3 3
3 5
1 3
1 3
3 2
1 6
3 6
3 2
1 8
1 9
1 4
3 4
3 1
3 12
1 6
3 11
3 3
3 9
3 2
3 7
3 10
1 7
3 3
1 9
3 13
3 4
3 6
1 6
1 1
3 11
3 8
1 1
1 1
3 9
1 4
3 9
3 2
3 20
1 8
1 8
3 11
1 8
3 6
1 6
3 19
1 5
1 9
1 9
3 10
3 16
1 6
3 2
1 9
3 11
3 11...

output:

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

result:

ok 194540 lines

Test #17:

score: 19
Accepted
time: 288ms
memory: 60440kb

input:

1 298768
1 0
1 0
1 2
1 2
1 0
1 0
1 1
1 6
1 0
1 7
1 9
1 10
1 6
3 11
1 4
3 8
1 10
1 6
3 15
1 5
1 8
3 18
1 0
1 10
1 9
1 0
1 3
1 3
1 0
1 9
1 1
1 10
1 6
1 1
3 16
1 8
1 0
3 15
1 9
1 2
1 3
1 3
1 10
3 18
1 8
3 8
1 10
1 7
1 6
3 22
1 5
3 35
1 1
3 38
1 8
1 10
3 6
1 6
1 3
1 0
3 36
1 8
1 3
1 2
3 29
1 4
1 4
1 3
1...

output:

2
5
15
7
10
31
16
14
3
28
16
10
31
14
24
51
58
76
43
3
14
67
7
27
18
33
75
6
89
12
21
88
14
34
1
84
10
18
49
24
60
87
80
116
16
148
72
99
101
157
102
1
159
101
57
149
159
164
112
74
89
43
194
131
135
10
31
85
91
187
84
66
136
61
217
58
114
76
116
182
31
114
124
228
91
124
20
109
154
258
203
136
162
...

result:

ok 74993 lines

Test #18:

score: 19
Accepted
time: 231ms
memory: 57640kb

input:

1 297636
1 0
3 1
1 0
3 2
3 2
1 0
3 2
1 0
1 0
3 5
3 3
1 5
1 0
3 2
1 0
1 6
1 9
1 0
1 8
1 0
3 2
3 3
3 2
1 3
3 14
3 13
1 0
1 0
3 16
1 0
3 12
1 5
1 0
1 0
1 8
1 0
1 8
1 0
1 5
1 2
3 14
1 0
1 0
1 0
1 0
1 0
3 14
1 0
1 9
1 0
3 26
1 0
3 25
3 1
3 15
1 0
1 0
3 34
3 1
1 9
1 0
1 0
3 17
1 2
1 8
1 0
3 31
1 10
1 0
1 ...

output:

1
1
1
2
1
3
6
12
11
12
12
1
1
7
23
28
33
24
35
15
4
37
17
9
7
25
29
12
37
47
13
38
45
5
6
50
51
49
57
47
19
16
46
60
55
51
49
18
59
6
70
17
59
12
65
61
86
57
51
92
43
12
11
46
64
39
47
85
27
111
79
14
41
12
1
47
28
23
13
130
87
92
67
73
16
68
66
51
118
158
145
78
99
34
42
157
161
97
166
169
171
106
...

result:

ok 98914 lines

Test #19:

score: 19
Accepted
time: 234ms
memory: 52568kb

input:

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

output:

3
1
4
5
3
3
6
2
3
7
1
6
1
5
5
4
10
11
6
9
11
4
2
4
8
8
1
4
12
4
10
11
9
8
4
3
19
9
15
3
11
21
23
19
9
5
21
13
25
13
15
30
30
12
17
17
11
28
30
12
15
32
20
8
6
20
6
29
18
36
21
15
13
21
2
40
18
5
42
5
15
29
50
7
8
23
49
30
27
14
26
60
52
4
15
25
56
10
44
21
61
45
25
4
34
59
64
65
64
33
50
64
47
34
63...

result:

ok 166650 lines

Subtask #3:

score: 21
Accepted

Test #20:

score: 21
Accepted
time: 202ms
memory: 48276kb

input:

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

output:

2
2
1
1
4
2
4
1
1
8
5
10
5
10
8
5
8
9
8
11
1
2
1
8
6
11
9
3
2
4
4
9
3
15
13
12
4
9
4
12
10
6
2
4
10
9
16
2
15
13
13
7
3
3
11
21
7
5
4
2
10
5
15
20
6
17
12
5
24
4
15
13
7
10
17
6
19
9
19
19
12
3
18
16
21
19
26
12
25
21
19
10
14
24
8
8
14
16
32
8
14
33
30
14
4
1
20
21
37
22
25
7
18
27
28
35
37
18
33
4...

result:

ok 222965 lines

Test #21:

score: 21
Accepted
time: 205ms
memory: 51360kb

input:

2 297805
1 0
1 0
3 1
3 1
1 0
1 1
3 2
1 0
3 4
3 3
3 3
3 3
3 4
3 3
1 0
3 4
1 2
3 2
3 7
1 5
1 0
1 0
1 10
3 5
3 6
1 0
1 0
1 0
3 9
1 0
3 3
1 0
1 0
3 13
3 15
3 2
3 15
3 6
3 2
3 17
1 5
3 14
3 9
1 1
3 5
3 10
3 13
3 17
3 7
1 0
3 20
3 6
3 14
1 0
1 4
3 10
3 19
1 0
3 6
3 5
3 13
3 4
3 19
1 7
3 14
3 6
3 15
3 20
3...

output:

2
2
2
5
2
2
2
5
2
6
4
5
5
4
6
11
5
3
14
3
10
14
1
4
9
11
7
5
1
16
1
11
5
9
20
13
14
8
22
21
7
13
6
3
3
15
22
2
11
7
10
17
13
10
13
20
17
5
33
10
12
28
9
26
27
12
36
18
2
22
2
24
35
34
4
4
12
34
35
8
18
14
1
38
33
10
35
10
7
5
27
54
47
7
42
16
12
15
46
45
18
24
29
28
51
50
40
42
16
46
22
9
28
46
4
1
...

result:

ok 197988 lines

Test #22:

score: 21
Accepted
time: 429ms
memory: 60312kb

input:

2 292846
1 0
3 1
3 1
1 1
1 1
1 3
1 0
1 0
1 5
1 7
3 2
3 4
1 8
1 1
1 6
1 8
1 7
1 1
1 10
1 9
3 6
1 5
1 6
3 7
1 3
1 3
1 5
1 6
1 4
1 6
1 1
1 6
1 9
1 5
3 23
1 7
1 8
1 3
1 1
1 4
3 8
1 6
1 1
1 8
1 2
1 5
1 3
1 5
1 9
3 25
1 10
1 6
1 9
3 44
1 7
3 26
1 1
1 7
1 5
1 9
3 34
1 9
1 3
1 6
1 0
1 6
1 0
1 9
3 53
1 10
1 ...

output:

1
1
8
7
1
6
27
14
28
23
4
3
2
57
9
34
43
87
64
13
1
63
88
2
83
38
89
101
97
82
57
115
145
57
34
57
15
147
126
107
108
140
37
91
177
16
135
205
227
171
152
88
31
95
21
231
40
20
273
201
128
82
98
147
115
169
238
129
58
179
114
268
324
39
163
132
251
230
65
16
295
299
15
272
28
312
255
358
315
229
193...

result:

ok 58684 lines

Test #23:

score: 21
Accepted
time: 316ms
memory: 57616kb

input:

2 294522
1 0
1 0
3 2
1 2
1 1
3 1
3 2
1 4
3 2
1 0
1 5
3 6
3 7
1 1
3 8
1 2
1 3
1 10
3 4
3 3
3 1
1 4
1 4
3 6
1 9
1 13
3 8
1 9
1 13
1 9
3 3
3 16
3 2
3 3
3 18
3 16
1 10
3 9
1 14
3 19
1 12
3 6
3 10
1 13
3 2
1 21
1 15
1 21
3 5
1 24
1 25
1 23
1 26
1 23
3 27
1 30
1 24
1 26
1 29
1 30
1 34
1 28
1 34
3 25
1 33
...

output:

1
3
1
1
1
7
5
9
4
7
1
9
7
5
2
7
4
5
3
10
1
9
2
24
25
29
4
15
17
8
12
23
32
28
44
43
4
14
29
28
63
59
57
63
12
60
57
63
50
12
11
54
19
2
41
71
55
72
70
66
29
65
89
21
56
3
75
56
62
65
67
22
6
108
109
62
7
56
51
43
80
118
101
87
18
83
109
19
77
91
88
19
24
31
83
87
146
13
106
52
133
44
93
56
84
51
139...

result:

ok 117694 lines

Test #24:

score: 21
Accepted
time: 228ms
memory: 55752kb

input:

2 295234
1 0
1 1
3 1
3 2
3 1
1 0
3 2
3 3
3 3
3 3
3 2
1 0
1 2
3 1
1 5
1 0
1 1
1 4
1 7
1 1
1 1
3 1
1 10
1 0
3 8
1 0
1 0
3 12
1 8
3 9
1 0
3 3
3 9
3 7
3 12
3 15
1 0
1 0
1 0
3 16
3 7
1 1
1 0
3 9
3 15
3 18
1 0
1 7
1 0
3 22
3 21
3 24
3 14
3 25
1 9
1 0
1 0
1 6
3 2
1 3
1 0
1 0
1 7
1 0
1 0
1 0
1 0
1 0
1 0
1 0...

output:

1
2
1
3
1
1
1
3
3
6
11
11
8
10
9
5
12
3
5
8
13
7
5
19
4
2
10
12
27
34
19
39
29
3
31
12
13
29
10
33
18
51
46
55
6
7
22
38
49
17
9
30
30
43
17
40
44
23
52
21
18
61
56
71
14
4
55
46
50
20
51
19
31
16
50
3
13
58
7
85
21
41
14
90
22
74
65
64
10
2
62
75
21
49
82
4
71
11
6
99
44
50
58
45
1
58
46
80
65
68
4...

result:

ok 147378 lines

Test #25:

score: 21
Accepted
time: 231ms
memory: 55652kb

input:

2 290392
1 0
3 1
3 1
1 1
3 1
1 0
3 2
1 0
3 2
3 4
1 3
3 4
1 4
3 2
3 1
1 2
1 4
1 4
3 3
3 8
1 1
3 1
3 10
1 1
3 7
1 4
3 12
3 1
1 10
3 10
3 12
1 13
3 6
1 8
1 11
3 8
3 10
3 1
3 2
3 13
1 14
3 3
1 8
3 8
1 18
3 10
3 3
1 14
1 12
1 18
1 15
3 11
3 1
3 19
1 14
1 17
3 5
1 23
3 14
1 24
1 26
1 20
3 8
3 8
3 13
1 22
...

output:

1
1
1
3
4
1
1
6
5
5
3
7
8
11
2
8
10
2
5
4
12
9
15
13
7
4
14
9
15
14
8
13
20
5
5
20
13
20
29
20
23
18
2
15
3
19
5
8
10
29
47
22
49
45
34
20
32
2
40
30
41
15
6
36
11
48
7
35
73
37
8
30
37
63
82
30
35
60
4
27
15
44
18
34
1
21
78
39
54
58
23
53
46
31
11
32
70
100
22
94
105
58
117
13
35
22
51
114
87
70
9...

result:

ok 144784 lines

Test #26:

score: 21
Accepted
time: 222ms
memory: 56176kb

input:

2 290273
1 0
1 0
3 1
1 0
1 0
3 4
1 0
3 4
3 3
3 1
1 0
3 3
1 0
3 5
3 4
3 1
3 2
1 0
3 6
1 0
1 7
3 6
1 2
1 1
1 5
3 4
1 3
3 9
1 10
3 4
3 9
1 4
1 0
1 0
3 6
3 1
1 0
1 6
3 16
1 10
1 9
1 0
1 0
1 0
1 2
3 21
1 6
1 0
1 0
3 24
1 1
1 0
1 0
3 26
3 18
1 9
1 6
1 0
3 35
1 4
3 36
1 0
1 5
1 8
1 5
1 2
3 36
1 0
1 6
1 0
1...

output:

2
1
2
3
5
4
3
4
7
6
3
5
8
1
9
1
8
17
14
12
4
28
9
1
27
31
42
23
25
37
14
13
4
16
2
7
37
36
39
43
10
33
30
11
9
53
42
26
7
56
77
63
55
11
44
78
23
69
14
87
54
28
52
17
49
15
26
92
47
93
92
105
16
116
94
1
40
85
77
82
60
94
120
97
31
85
56
10
32
61
133
136
80
60
73
60
115
104
21
30
18
164
96
8
149
83
...

result:

ok 116141 lines

Test #27:

score: 21
Accepted
time: 259ms
memory: 55704kb

input:

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

output:

1
2
2
7
2
5
14
5
18
16
6
2
13
21
23
2
3
17
2
18
37
4
4
7
23
7
41
35
16
21
42
23
26
47
55
47
47
26
58
35
37
37
24
13
52
23
68
29
32
66
12
13
50
29
6
11
13
52
78
70
47
55
38
17
5
81
9
31
4
5
46
85
91
86
94
68
76
16
53
58
54
48
16
84
45
22
47
43
26
92
17
72
111
31
20
63
16
68
75
89
42
106
81
111
81
58
...

result:

ok 147525 lines

Test #28:

score: 21
Accepted
time: 218ms
memory: 55748kb

input:

2 295559
1 0
1 0
3 1
3 1
3 1
3 2
3 2
1 0
3 2
1 1
1 1
3 5
1 4
1 1
1 0
1 0
3 4
1 0
1 0
1 0
1 1
1 9
1 0
1 1
1 9
3 3
1 9
3 9
3 11
1 9
1 0
3 14
1 0
3 15
3 10
1 3
3 20
3 3
1 0
1 0
3 1
1 5
3 5
3 18
3 19
1 5
1 4
1 10
3 4
3 1
3 13
1 0
1 6
3 16
1 0
1 0
3 21
1 0
3 22
1 7
3 24
1 4
3 31
3 11
3 8
1 0
1 0
3 12
3 3...

output:

2
2
2
1
1
2
4
8
9
5
3
10
3
6
2
13
18
22
11
10
26
19
21
21
6
21
5
3
11
19
12
2
1
35
26
8
39
34
39
17
32
13
7
26
37
30
17
9
15
49
50
10
48
51
57
53
1
28
7
53
44
15
4
22
53
62
14
44
47
60
46
55
9
57
6
63
45
56
32
3
24
3
3
66
69
34
77
77
11
70
88
73
87
46
21
53
88
68
6
24
69
63
50
77
46
7
39
45
98
50
14...

result:

ok 148070 lines

Test #29:

score: 21
Accepted
time: 231ms
memory: 56956kb

input:

2 294051
1 0
1 1
1 0
1 0
1 4
3 1
3 1
1 0
3 3
3 5
1 5
1 6
1 1
1 0
3 8
3 10
1 0
1 0
1 0
1 0
1 0
1 3
3 9
1 0
3 7
1 9
1 0
1 0
1 0
1 1
3 11
1 0
1 0
1 0
1 4
3 15
1 0
1 0
1 6
1 0
1 0
1 2
3 8
1 3
3 5
1 5
1 0
1 0
1 0
1 2
3 18
1 0
3 4
1 0
1 0
1 0
1 5
1 9
1 6
1 0
1 0
1 0
1 1
1 8
1 0
1 0
1 1
1 0
3 29
1 5
3 40
3...

output:

4
4
4
3
3
1
15
12
9
8
20
23
35
25
33
9
43
19
48
14
46
49
37
56
45
21
43
27
64
35
38
76
68
19
79
9
1
24
96
98
52
47
57
2
88
113
82
21
36
77
8
74
38
46
67
32
124
29
90
114
54
28
68
38
33
109
103
6
58
112
37
78
68
128
24
13
76
131
144
103
162
96
122
159
68
157
46
106
2
134
114
211
152
143
42
123
98
170...

result:

ok 97860 lines

Test #30:

score: 21
Accepted
time: 243ms
memory: 57684kb

input:

2 291529
1 0
1 1
1 1
3 1
1 3
1 2
1 0
1 1
1 4
1 2
1 0
1 0
1 1
3 12
1 0
3 1
1 10
1 0
1 2
1 0
1 3
1 6
1 0
1 0
3 11
1 3
1 4
1 0
1 0
1 0
1 3
1 0
1 9
1 10
1 8
1 0
1 4
3 1
1 0
1 0
1 0
3 34
3 15
3 11
3 22
1 0
1 0
1 7
1 0
3 9
1 0
1 0
1 0
3 5
1 6
1 0
3 37
1 7
1 0
1 0
3 14
1 10
1 3
1 3
1 0
1 1
1 0
3 8
1 0
1 0
...

output:

1
5
5
6
17
3
12
14
25
38
43
7
26
48
28
19
38
31
29
16
14
57
58
66
64
55
58
71
22
57
50
76
69
17
3
26
37
61
62
55
22
60
11
91
89
48
42
32
55
34
9
7
78
2
83
38
16
12
42
31
41
52
18
46
81
53
103
75
113
66
12
76
50
75
120
77
81
83
116
106
99
141
144
24
20
43
49
109
67
101
66
12
54
23
96
93
10
129
102
22...

result:

ok 96730 lines

Test #31:

score: 21
Accepted
time: 256ms
memory: 57060kb

input:

2 294537
1 0
1 0
3 1
3 2
1 2
1 3
3 1
3 3
1 1
1 5
1 4
3 7
1 7
1 1
3 6
3 7
3 2
1 5
1 6
3 2
1 2
1 11
1 7
3 4
3 12
3 9
1 12
1 13
1 16
1 14
3 10
1 10
3 15
3 7
1 17
1 18
1 19
1 17
1 21
1 15
1 22
1 18
1 22
1 23
1 28
3 16
1 26
3 26
1 24
1 30
1 25
1 34
1 27
3 20
1 28
3 14
3 15
3 29
1 28
1 38
1 39
3 19
1 33
1...

output:

2
1
4
2
4
9
4
1
1
4
2
9
13
3
6
26
22
36
10
3
36
22
1
41
48
7
46
23
40
29
23
20
24
29
31
28
15
36
62
24
65
23
71
22
101
13
30
48
37
34
68
54
12
3
59
70
92
86
92
12
38
133
95
110
137
111
120
101
9
84
33
10
128
140
16
96
20
58
116
39
139
141
105
139
103
142
136
142
159
166
5
117
82
74
64
168
104
77
83
...

result:

ok 98247 lines

Test #32:

score: 21
Accepted
time: 204ms
memory: 54272kb

input:

2 293042
1 0
1 0
3 2
1 0
1 0
3 3
3 2
3 4
3 4
3 4
3 4
1 0
1 0
1 1
3 2
1 1
1 0
3 4
1 7
3 8
3 2
3 1
1 0
3 5
1 0
1 0
1 2
1 6
3 7
3 12
1 10
1 4
3 4
1 0
1 0
1 0
3 2
1 0
1 2
3 10
3 16
1 3
1 2
3 11
3 20
3 7
3 8
3 19
3 7
1 0
3 16
1 0
3 22
3 18
1 0
1 6
3 3
1 0
3 12
1 6
3 30
3 21
3 1
3 10
3 5
1 0
3 29
1 2
3 20...

output:

1
2
3
1
1
1
1
5
4
8
6
7
4
14
2
8
14
21
22
7
2
22
21
3
22
25
20
6
18
10
14
5
26
29
17
2
7
11
26
8
23
10
35
29
29
28
5
43
21
12
13
26
5
24
20
28
43
23
37
55
6
46
31
10
58
55
57
43
42
9
26
59
12
17
21
34
21
58
16
47
13
33
13
39
48
1
72
8
50
35
17
41
8
54
8
21
19
86
45
11
3
45
63
4
22
7
49
74
9
2
56
14
...

result:

ok 167688 lines

Test #33:

score: 21
Accepted
time: 264ms
memory: 55828kb

input:

2 294543
1 0
1 1
1 2
1 2
1 0
3 5
3 2
1 0
1 4
1 1
1 6
1 7
1 10
3 10
1 7
1 8
1 1
1 6
1 7
3 3
3 3
3 13
1 5
3 12
1 10
3 13
3 9
1 3
1 1
3 4
1 7
3 8
1 9
1 1
1 5
1 7
1 10
3 3
3 17
3 16
1 8
1 1
3 13
1 4
1 6
3 28
1 7
1 1
1 2
1 5
3 10
1 10
1 8
3 12
3 33
3 31
1 1
1 2
1 1
1 10
1 6
1 4
1 8
3 25
1 1
1 6
1 2
3 27
...

output:

1
3
9
16
16
8
14
9
3
12
9
25
7
19
15
10
29
29
21
25
32
24
20
40
20
38
21
10
5
21
47
1
53
2
37
45
14
15
65
50
33
43
37
60
41
41
43
70
29
61
75
58
17
30
20
20
34
16
68
14
25
26
110
30
43
113
68
97
103
4
3
64
38
9
51
88
108
10
68
88
101
67
74
102
106
24
86
136
45
156
84
68
80
103
145
134
21
141
153
155...

result:

ok 117234 lines

Test #34:

score: 21
Accepted
time: 232ms
memory: 53996kb

input:

2 299148
1 0
1 1
1 1
1 1
3 1
1 3
1 5
1 3
3 5
1 7
1 4
1 4
3 6
3 8
3 6
1 3
1 2
1 11
3 11
3 11
3 7
1 9
1 10
1 12
1 9
1 10
3 10
3 3
1 13
1 19
1 13
1 19
1 19
1 22
1 21
1 17
3 7
3 8
3 19
3 10
3 8
3 5
1 24
1 20
3 21
3 21
1 25
3 2
3 8
1 25
1 22
1 25
1 31
3 30
1 30
3 20
3 10
1 34
1 33
1 27
1 30
3 11
3 19
3 2...

output:

1
5
9
7
9
6
6
8
3
9
20
21
15
3
21
22
13
13
27
24
16
26
3
11
21
30
22
16
17
17
2
34
5
14
3
38
9
28
21
15
31
48
55
2
22
42
15
18
23
40
46
47
11
53
61
41
57
69
13
73
28
64
11
34
54
20
49
23
49
40
15
29
56
33
69
16
75
27
17
50
47
80
86
29
49
49
50
103
103
69
63
8
79
93
47
67
105
109
29
108
10
105
50
86
...

result:

ok 149568 lines

Subtask #4:

score: 23
Accepted

Test #35:

score: 23
Accepted
time: 491ms
memory: 50188kb

input:

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

output:

1
2
4
3
2
3
4
4
1
2
3
3
3
2
2
4
5
8
9
9
7
6
12
14
6
18
11
4
4
18
7
14
5
11
11
25
10
13
14
5
17
19
12
19
10
19
34
32
3
41
19
44
6
2
22
8
34
36
18
16
10
37
24
37
3
2
55
33
28
43
8
44
61
9
18
28
31
64
45
54
18
51
7
71
61
6
59
19
37
4
47
83
81
20
71
24
24
66
93
33
48
59
23
35
60
43
47
79
44
40
22
84
17
...

result:

ok 99743 lines

Test #36:

score: 23
Accepted
time: 489ms
memory: 52604kb

input:

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

output:

1
5
1
5
7
3
6
6
12
8
5
6
11
4
5
12
9
8
7
4
8
15
17
4
7
8
18
23
3
4
1
15
1
16
26
21
13
16
23
29
20
25
26
24
26
38
42
43
18
21
37
8
29
42
50
9
6
54
19
24
29
12
14
21
6
44
30
27
25
39
21
11
39
38
43
29
8
28
6
18
52
29
11
17
23
13
13
35
7
35
71
16
56
19
38
34
54
7
73
28
58
1
22
27
51
53
23
95
57
41
96
9...

result:

ok 99750 lines

Test #37:

score: 23
Accepted
time: 487ms
memory: 50700kb

input:

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

output:

1
1
2
2
1
1
4
2
3
6
5
8
9
4
4
3
11
1
11
16
9
14
9
9
9
15
22
5
5
13
22
10
18
15
27
6
7
35
14
22
28
38
3
3
4
16
11
8
26
15
35
30
27
21
37
19
16
56
4
32
54
32
18
19
13
22
44
28
62
22
2
77
28
79
60
44
78
46
34
45
5
35
8
61
16
59
60
1
76
11
19
86
11
51
59
73
23
104
96
35
88
66
9
10
85
23
83
85
97
81
97
1...

result:

ok 99683 lines

Subtask #5:

score: 33
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Test #38:

score: 33
Accepted
time: 429ms
memory: 51284kb

input:

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

output:

1
1
1
1
9
7
4
11
9
4
8
6
5
20
9
20
10
21
17
19
8
4
14
25
21
20
14
24
2
10
32
4
1
21
14
17
31
1
38
40
31
11
33
19
16
35
34
12
45
1
27
38
38
7
42
21
12
1
25
51
37
43
52
18
21
50
16
19
12
66
58
71
18
63
2
61
55
58
24
18
46
79
27
26
62
65
4
41
79
34
44
68
88
37
81
17
23
30
27
9
26
54
49
58
34
97
10
14
6...

result:

ok 98966 lines

Test #39:

score: 33
Accepted
time: 515ms
memory: 49356kb

input:

4 291314
1 0
1 0
1 0
2 1 0
2 3 1
3 3
2 3 0
2 2 1
2 3 2
2 1 0
2 1 0
2 1 0
3 2
3 3
2 2 0
3 2
2 3 2
2 1 0
2 1 0
3 3
2 1 0
1 0
2 1 0
1 0
2 1 0
3 1
2 2 0
2 3 0
2 5 4
3 3
2 5 1
2 5 3
2 4 3
2 2 0
3 5
2 1 0
2 3 1
2 3 1
2 1 0
1 2
2 6 4
3 2
2 5 0
2 6 3
2 4 1
3 4
2 2 0
1 4
2 4 2
2 2 0
2 4 0
3 2
2 6 2
1 0
2 8 3...

output:

3
2
3
1
2
5
3
2
1
4
4
6
6
6
6
4
5
10
16
19
4
23
24
1
7
22
20
22
5
22
5
29
3
10
42
8
28
41
11
11
39
41
39
2
1
28
46
20
20
37
1
27
35
6
16
2
27
11
45
44
31
56
41
55
56
52
53
20
32
36
5
58
45
7
33
29
69
5
63
63
34
58
57
20
32
36
9
26
48
45
73
59
17
26
13
19
52
83
20
63
30
43
51
8
29
101
28
62
81
91
77
...

result:

ok 48520 lines

Test #40:

score: 33
Accepted
time: 413ms
memory: 45648kb

input:

4 290886
1 0
2 1 0
2 1 0
2 1 0
2 1 0
2 1 0
2 1 0
2 1 0
3 1
2 1 0
1 0
3 1
2 2 0
2 2 1
3 1
1 0
2 1 0
2 1 0
3 3
3 1
2 2 1
3 2
3 3
2 2 1
1 0
3 2
3 2
2 4 1
2 2 0
3 1
3 4
3 4
2 4 0
2 1 0
3 1
1 1
3 2
3 5
2 1 0
2 2 1
3 5
2 1 0
2 2 0
2 1 0
2 2 1
2 1 0
2 4 3
3 1
3 5
3 2
3 2
3 4
1 0
2 4 2
2 6 4
3 2
3 3
2 3 2
2...

output:

1
2
1
1
2
3
1
4
4
3
4
4
4
3
5
4
3
4
5
5
2
4
1
3
3
8
7
5
5
2
2
9
9
8
10
3
1
4
14
9
14
6
12
13
3
4
6
8
15
1
12
5
4
14
8
17
14
21
13
13
15
11
14
11
5
21
19
22
2
8
19
3
8
3
5
14
17
12
27
1
1
10
31
24
26
17
3
10
22
28
4
36
8
20
3
6
36
7
20
24
28
16
13
1
16
7
11
25
5
38
36
20
34
5
21
13
11
9
41
39
26
15
3...

result:

ok 108743 lines

Test #41:

score: 33
Accepted
time: 432ms
memory: 52040kb

input:

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

output:

1
1
1
4
5
5
11
2
11
8
8
3
9
2
8
10
15
18
18
2
20
12
7
26
14
23
24
28
6
23
28
5
16
33
21
12
26
6
11
24
13
4
3
13
16
17
6
23
39
45
15
25
27
8
43
38
35
69
67
13
52
39
63
42
61
40
53
51
45
71
51
40
67
67
25
81
18
22
75
35
68
24
40
13
65
39
64
77
55
17
76
83
62
6
37
65
37
12
38
13
21
37
90
35
55
67
17
20...

result:

ok 87130 lines

Test #42:

score: 33
Accepted
time: 434ms
memory: 51864kb

input:

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

output:

2
4
1
3
1
2
4
4
8
7
10
11
13
25
27
14
18
3
2
7
29
23
33
5
47
26
23
39
40
50
21
2
33
10
50
24
14
69
24
23
83
14
50
44
69
13
77
42
13
42
13
56
4
79
52
89
33
60
46
79
65
66
59
11
29
88
48
101
73
86
45
66
60
136
6
17
59
78
142
143
79
51
58
75
51
35
150
140
148
143
48
63
51
42
155
46
29
32
128
16
39
49
1...

result:

ok 74076 lines

Test #43:

score: 33
Accepted
time: 426ms
memory: 49708kb

input:

4 294378
1 0
3 1
2 1 0
2 1 0
2 1 0
3 1
2 1 0
3 1
2 1 0
3 1
2 1 0
1 1
3 1
1 2
3 3
1 0
1 4
3 2
2 1 0
3 5
1 1
1 2
2 6 0
2 5 1
2 6 0
1 6
2 4 2
1 0
2 4 1
2 8 6
3 5
3 8
3 2
1 8
2 8 4
1 3
1 2
2 5 3
3 4
3 7
3 10
2 10 6
2 4 3
2 1 0
2 8 7
2 3 0
2 3 0
3 6
2 3 1
3 7
2 12 1
1 9
2 8 2
1 5
3 6
3 7
3 8
2 1 0
2 3 0
...

output:

1
1
1
1
1
3
4
2
5
3
7
4
9
6
2
11
3
14
13
14
11
7
1
6
12
11
7
1
20
11
13
25
10
8
10
6
5
24
17
29
19
12
25
27
33
32
36
28
7
20
18
30
5
55
36
11
37
34
45
35
17
31
11
55
37
14
25
49
23
52
14
30
42
14
2
48
87
8
12
75
38
8
21
58
30
14
32
10
23
26
21
19
77
28
21
26
64
96
20
108
86
11
61
90
49
62
113
3
102
...

result:

ok 88582 lines

Test #44:

score: 33
Accepted
time: 273ms
memory: 47924kb

input:

4 298519
1 0
3 1
3 1
1 0
3 2
3 2
1 1
3 1
2 1 0
1 2
2 2 0
2 2 1
3 4
3 4
3 2
3 3
3 3
2 1 0
1 4
3 5
3 3
3 1
3 3
3 3
3 2
1 0
3 3
3 4
3 4
3 1
1 2
3 6
3 1
3 4
3 2
3 3
3 2
3 1
2 4 3
3 2
3 2
1 0
1 0
3 5
3 9
3 7
2 8 7
3 5
3 2
3 2
1 0
3 1
2 7 5
3 2
2 5 0
2 9 8
1 0
1 0
3 9
3 7
3 6
1 10
2 10 1
3 11
3 1
1 0
3 11...

output:

1
1
1
1
2
4
4
3
2
2
5
2
1
2
2
3
3
5
5
2
1
2
6
4
3
4
2
6
6
7
1
9
6
7
7
4
10
8
6
4
2
8
3
6
8
12
7
13
8
5
5
2
6
15
2
14
8
5
4
2
7
15
13
10
15
7
3
14
19
3
7
1
5
14
5
8
12
6
1
6
5
9
13
17
12
19
20
18
8
9
2
10
13
19
13
12
16
14
19
17
7
2
1
9
5
11
17
18
13
5
6
19
17
2
21
25
25
16
8
14
25
25
16
24
10
25
7
5...

result:

ok 198778 lines

Test #45:

score: 33
Accepted
time: 348ms
memory: 48296kb

input:

4 290130
1 0
3 1
1 1
3 1
2 1 0
3 1
1 1
3 2
3 3
1 2
2 4 1
3 4
1 3
1 5
2 6 4
2 2 0
3 1
3 5
2 2 0
3 4
2 2 1
3 6
1 6
3 3
3 6
3 3
3 5
2 3 0
3 7
3 3
2 5 4
1 0
3 5
1 1
2 6 1
1 6
2 7 5
1 1
3 10
3 10
2 2 0
3 6
3 8
3 11
3 8
3 9
1 5
1 9
2 4 3
2 7 2
3 5
1 6
3 10
3 9
3 14
3 14
3 13
2 10 9
3 7
3 13
3 6
3 13
3 5
1...

output:

1
1
1
3
2
2
2
6
3
3
5
3
5
6
6
1
7
7
7
7
1
5
1
6
4
14
10
13
13
11
7
11
13
11
4
5
2
6
7
6
3
9
10
15
3
6
14
15
6
4
5
8
2
17
11
18
8
12
16
15
6
18
9
10
24
12
14
20
19
25
20
6
12
8
9
24
5
16
20
28
19
28
30
1
8
31
8
23
2
19
28
11
2
3
3
36
16
1
17
3
24
9
7
26
15
4
22
28
37
29
17
4
30
11
14
43
7
24
12
32
12...

result:

ok 145139 lines

Test #46:

score: 33
Accepted
time: 361ms
memory: 47328kb

input:

4 294275
1 0
2 1 0
2 1 0
3 1
2 1 0
2 1 0
3 1
2 1 0
3 1
3 1
2 1 0
1 0
2 1 0
3 2
3 1
2 2 0
3 2
3 1
3 2
3 2
3 1
3 2
2 2 1
2 1 0
3 2
2 2 1
2 1 0
3 2
3 2
2 2 0
1 0
3 2
3 2
3 1
2 2 0
2 3 2
2 3 2
1 0
2 3 1
3 3
2 4 2
3 3
3 4
3 4
2 1 0
2 2 1
2 2 0
3 1
2 1 0
1 2
1 0
2 3 0
3 3
2 1 0
3 3
2 5 3
2 4 3
2 3 2
3 4
3...

output:

1
1
1
1
1
2
1
2
1
1
2
1
2
2
2
2
2
3
4
4
2
2
3
2
2
5
2
6
1
2
1
8
1
7
1
6
7
7
4
7
1
4
6
7
5
5
5
9
9
3
6
9
8
8
1
3
1
1
1
2
1
10
5
10
6
6
10
5
2
3
7
4
10
9
7
4
10
10
4
8
2
4
9
3
2
5
6
16
11
2
5
9
15
3
10
13
7
2
15
3
10
2
20
19
12
5
2
10
5
11
19
23
6
9
9
10
24
18
19
14
9
18
26
22
9
24
6
27
6
29
26
20
12
...

result:

ok 147109 lines

Test #47:

score: 33
Accepted
time: 379ms
memory: 52100kb

input:

4 292773
1 0
1 0
1 1
2 3 1
3 3
1 3
3 4
1 4
3 3
2 3 1
2 5 1
3 3
1 2
3 4
1 6
2 6 5
2 7 5
3 3
1 1
1 6
3 3
1 4
2 7 3
1 6
3 2
1 7
1 10
3 9
2 7 1
1 10
3 5
3 14
3 11
3 2
2 14 10
1 6
1 11
3 16
2 4 3
2 15 2
2 7 4
2 1 0
3 8
3 5
2 1 0
1 9
3 11
3 16
2 3 0
2 11 0
2 16 4
3 3
1 8
1 14
2 3 1
3 7
2 6 5
1 15
2 19 17
...

output:

3
4
3
4
6
6
8
1
7
6
13
8
1
10
4
5
7
8
2
18
9
10
12
22
4
20
8
10
6
24
21
18
3
12
22
25
34
12
9
22
1
8
37
16
36
4
36
9
11
26
8
26
36
31
36
7
42
40
18
19
24
46
30
23
41
31
33
48
38
30
20
26
27
50
10
52
30
1
46
7
20
34
57
12
51
30
27
60
10
51
6
58
61
72
37
4
2
8
35
5
24
44
20
9
49
49
24
52
13
65
37
6
82...

result:

ok 116820 lines

Test #48:

score: 33
Accepted
time: 346ms
memory: 49372kb

input:

4 299354
1 0
3 1
2 1 0
2 1 0
3 1
1 1
2 1 0
3 2
3 2
2 2 1
3 1
2 1 0
2 2 1
1 0
2 1 0
3 1
3 3
2 3 1
2 1 0
3 2
2 3 2
2 2 1
1 0
1 0
3 4
1 0
3 5
3 2
2 6 0
1 2
1 0
1 0
3 2
3 5
3 9
2 3 2
2 1 0
3 9
2 5 3
2 8 4
1 5
1 0
1 7
1 0
1 2
1 9
3 11
1 5
1 5
3 3
2 14 6
3 13
1 10
2 11 10
3 5
2 9 2
1 1
2 4 1
2 9 1
1 0
3 9...

output:

1
1
2
2
1
2
1
3
2
2
5
7
4
1
1
2
13
1
13
7
16
20
4
5
2
7
6
9
15
15
11
6
18
4
13
13
16
27
8
21
14
25
31
2
20
27
15
30
10
20
6
32
20
5
30
24
19
8
2
17
16
31
18
5
35
7
17
9
2
33
21
16
32
8
5
33
15
7
3
39
25
18
27
11
20
4
35
9
42
37
14
33
10
9
5
3
1
46
1
35
9
14
45
21
3
14
21
25
11
3
34
9
1
38
28
23
1
35...

result:

ok 150091 lines

Test #49:

score: 33
Accepted
time: 448ms
memory: 52848kb

input:

4 290826
1 0
3 1
1 1
1 2
1 1
2 1 0
1 2
2 5 1
1 0
3 6
2 2 1
3 1
1 6
1 1
1 6
2 3 1
3 8
1 9
2 7 6
2 4 2
1 1
2 8 7
2 2 1
2 3 1
1 3
2 11 10
1 5
2 12 6
1 9
1 10
1 7
3 5
2 5 0
1 0
1 7
3 10
2 7 5
1 3
1 4
2 7 1
1 3
3 8
2 2 1
3 3
2 20 18
2 12 11
2 10 1
2 13 12
2 8 6
2 16 2
1 2
3 17
2 5 2
3 17
1 5
1 3
3 12
1 1...

output:

1
1
2
5
12
6
15
16
1
1
10
25
28
12
3
8
25
26
27
2
38
46
39
64
29
66
13
57
40
67
16
68
53
38
8
14
24
102
5
82
98
59
9
108
84
52
24
34
27
77
92
77
81
123
131
122
65
81
34
82
31
76
102
93
30
71
136
80
77
142
70
140
67
66
51
138
89
179
87
65
105
116
59
34
181
77
60
94
123
112
148
192
181
83
206
208
34
2...

result:

ok 64514 lines

Test #50:

score: 33
Accepted
time: 312ms
memory: 54148kb

input:

4 291569
1 0
1 1
3 2
3 2
3 2
1 1
1 2
3 4
1 1
1 1
3 2
2 6 4
2 6 4
1 1
1 7
1 2
1 8
1 6
3 7
1 11
1 10
1 5
1 6
3 6
3 4
1 7
1 15
1 9
1 18
3 12
1 19
3 7
1 14
3 9
1 14
3 16
3 10
1 16
1 22
3 10
3 20
2 13 12
1 23
3 21
3 16
1 22
3 11
1 24
1 24
1 24
1 25
2 15 9
1 24
1 29
2 4 2
3 9
1 23
3 10
2 22 10
1 27
1 31
1...

output:

2
2
2
4
5
2
12
11
19
2
12
3
5
6
18
12
3
24
22
9
21
17
28
17
34
11
35
45
3
22
17
2
22
37
10
15
52
39
52
42
47
61
51
50
16
2
35
22
60
18
67
26
45
58
70
42
59
3
52
33
58
40
78
5
54
12
60
80
4
79
98
57
40
26
26
64
57
19
103
23
36
35
33
61
7
71
74
7
30
113
20
69
105
2
49
110
50
117
89
89
67
32
12
125
21
...

result:

ok 109540 lines

Test #51:

score: 33
Accepted
time: 286ms
memory: 48036kb

input:

4 295666
1 0
3 1
3 1
2 1 0
2 1 0
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
2 1 0
2 1 0
3 1
3 1
3 1
1 1
2 1 0
2 1 0
3 2
1 1
1 3
2 4 3
3 3
3 4
3 2
2 2 0
3 1
3 2
3 4
3 3
2 3 1
3 2
3 1
3 1
3 3
3 1
3 1
1 4
3 2
2 2 1
3 5
2 2 0
3 3
2 5 3
2 2 0
1 4
2 2 0
2 3 2
1 1
1 2
2 1 0
2 3 0
3 8
3...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
3
4
2
1
4
3
1
2
2
3
2
2
1
4
3
6
8
5
3
3
6
8
2
1
3
9
4
5
8
5
5
6
8
8
5
8
4
2
8
5
2
10
6
8
5
6
1
5
6
3
3
4
2
13
12
4
4
4
13
5
2
11
4
13
12
10
6
11
12
7
12
9
3
9
15
9
15
17
5
20
4
7
17
13
4
2
4
16
21
14
3
5
9
10
1
1
13
17
4
14
1
12
15
16
7
6
24
20
18
16
6
2...

result:

ok 197757 lines

Test #52:

score: 33
Accepted
time: 352ms
memory: 54028kb

input:

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

output:

1
1
1
1
1
3
1
3
5
1
6
5
1
9
5
10
2
14
11
2
14
4
12
2
8
17
12
17
4
14
8
16
15
16
13
11
2
9
23
25
23
9
12
11
29
20
32
37
15
31
33
24
36
36
30
29
27
19
7
28
21
46
16
25
10
40
8
8
55
31
38
18
43
37
18
60
7
33
29
52
19
14
59
58
36
13
41
18
45
62
54
40
20
27
6
55
47
64
18
62
73
20
4
40
64
70
60
35
14
7
18...

result:

ok 119220 lines