QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#54270#121. Bitaro's Partyprxms14 794ms412788kbC++2.6kb2022-10-07 18:29:592022-10-07 18:30:00

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-07 18:30:00]
  • 评测
  • 测评结果:14
  • 用时:794ms
  • 内存:412788kb
  • [2022-10-07 18:29:59]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 5;
const int SQ = 320;
vector<int> g[maxn];
vector<pair<int , int> > BSQ[maxn];
bool vis[maxn] , mark[maxn];
int n , m , q;

void relax(int v){
	for(int u : g[v]){
		vector<pair<int , int> > vec;
		while(!BSQ[v].empty()){
			vec.push_back(BSQ[v].back());
			BSQ[v].pop_back();
		}

		int jv = 0 , ju = 0;
		while(ju < (int)BSQ[u].size() && jv < (int)vec.size() && BSQ[v].size() < SQ){
			while(ju < (int)BSQ[u].size() && vis[BSQ[u][ju].second])
				ju++;
			while(jv < (int)vec.size() && vis[vec[jv].second])
				jv++;
			if(ju == (int)BSQ[u].size() || jv == (int)vec.size())
				break;
			if(BSQ[u][ju].first + 1 > vec[jv].first){
				BSQ[v].push_back({BSQ[u][ju].first + 1 , BSQ[u][ju].second});
				vis[BSQ[u][ju].second] = true;
				ju++;
			}
			else{
				BSQ[v].push_back(vec[jv]);
				vis[vec[jv].second] = true;
				jv++;
			}
		}

		while(ju < (int)BSQ[u].size() && BSQ[v].size() < SQ){
			while(ju < (int)BSQ[u].size() && vis[BSQ[u][ju].second])
				ju++;
			if(ju == (int)BSQ[u].size())
				break;
			BSQ[v].push_back({BSQ[u][ju].first + 1 , BSQ[u][ju].second});
			ju++;
		}

		while(jv < (int)vec.size() && BSQ[v].size() < SQ){
			while(jv < (int)vec.size() && vis[vec[jv].second])
				jv++;
			if(jv == (int)vec.size())
				break;
			BSQ[v].push_back(vec[jv]);
			jv++;
		}

		if(BSQ[v].size() < SQ && !vis[u]){
			BSQ[v].push_back({1 , u});
			vis[u] = true;
		}

		for(auto i : BSQ[v])
			vis[i.second] = false;
	}
}

int main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n >> m >> q;
	for(int i = 0 ; i < m ; i++){
		int u , v;
		cin >> u >> v;
		g[v].push_back(u);
	}

	for(int i = 1 ; i <= n ; i++)
		relax(i);

	while(q--){
		int ver , k;
		cin >> ver >> k;
		vector<int> in;
		for(int i = 0 ; i < k ; i++){
			int x;
			cin >> x;
			in.push_back(x);
			mark[x] = true;
		}

		if(k < SQ){
			int ans = -1;
			for(auto i : BSQ[ver]){
				if(!mark[i.second]){
					ans = max(ans , i.first);
				}
			}

			if(ans == -1){
				if(mark[ver]){
					cout << -1 << '\n';
				}
				else{
					cout << 0 << '\n';
				}
			}
			else{
				cout << ans << '\n';
			}
		}
		else{
			int dp[ver + 1];
			for(int i = 1 ; i <= ver ; i++){
				dp[i] = 0;
				for(int u : g[i]){
					if(dp[u] == -1) continue;
					dp[i] = max(dp[i] , dp[u] + 1);
				}

				if(dp[i] == 0 && mark[i]){
					dp[i] = -1;
				}
			}

			cout << dp[ver] << '\n';
		}

		for(int i : in)
			mark[i] = false;
	}
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 7
Accepted

Test #1:

score: 7
Accepted
time: 2ms
memory: 8300kb

input:

1 0 1
1 0

output:

0

result:

ok single line: '0'

Test #2:

score: 0
Accepted
time: 2ms
memory: 8236kb

input:

1 0 1
1 1 1

output:

-1

result:

ok single line: '-1'

Test #3:

score: 0
Accepted
time: 0ms
memory: 8404kb

input:

2 1 1
1 2
1 2 1 2

output:

-1

result:

ok single line: '-1'

Test #4:

score: 0
Accepted
time: 4ms
memory: 8192kb

input:

2 1 1
1 2
1 1 1

output:

-1

result:

ok single line: '-1'

Test #5:

score: 0
Accepted
time: 2ms
memory: 8720kb

input:

1000 2000 1
66 427
211 505
213 674
56 131
180 883
127 167
228 262
42 50
386 688
346 943
170 396
127 150
169 192
253 706
96 497
141 277
317 711
792 802
244 469
24 702
135 252
31 764
52 95
701 900
473 832
510 691
14 474
158 488
422 491
228 897
318 622
195 548
479 626
525 728
53 109
133 854
392 416
34 ...

output:

12

result:

ok single line: '12'

Test #6:

score: 0
Accepted
time: 2ms
memory: 8844kb

input:

1000 2000 1
762 826
799 904
17 20
56 733
46 416
261 768
196 392
121 144
14 69
244 625
331 485
331 383
502 635
107 914
131 274
288 495
70 103
417 934
318 535
775 930
9 113
250 677
82 200
2 4
36 77
367 553
8 31
633 712
21 179
484 963
117 146
207 413
685 787
561 903
508 710
834 912
4 76
196 977
355 394...

output:

14

result:

ok single line: '14'

Test #7:

score: 0
Accepted
time: 5ms
memory: 8756kb

input:

1000 2000 1
86 222
107 710
207 983
80 929
4 5
685 963
758 769
228 274
34 35
14 26
614 786
383 679
41 62
125 522
619 851
175 359
253 492
127 182
27 367
111 221
170 453
519 612
137 191
254 301
53 148
214 824
31 374
402 795
25 26
177 461
301 614
574 798
82 104
137 625
86 575
32 364
37 183
131 270
113 6...

output:

2

result:

ok single line: '2'

Test #8:

score: 0
Accepted
time: 7ms
memory: 11524kb

input:

1000 2000 1
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 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52...

output:

181

result:

ok single line: '181'

Test #9:

score: 0
Accepted
time: 23ms
memory: 11484kb

input:

1000 2000 1
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 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52...

output:

627

result:

ok single line: '627'

Test #10:

score: 0
Accepted
time: 12ms
memory: 11408kb

input:

1000 2000 1
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 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52...

output:

72

result:

ok single line: '72'

Test #11:

score: 0
Accepted
time: 13ms
memory: 11072kb

input:

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

output:

9

result:

ok single line: '9'

Test #12:

score: 0
Accepted
time: 10ms
memory: 9472kb

input:

1000 2000 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
3 17
16 18
2 19
18 20
1 21
1 22
13 23
15 24
6 25
1 26
1 27
1 28
1 29
2 30
1 31
1 32
26 33
11 34
8 35
1 36
19 37
30 38
29 39
24 40
10 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
29 51
22 52
49 53
7 54
1 55
1 56
9 57
44...

output:

11

result:

ok single line: '11'

Test #13:

score: 0
Accepted
time: 12ms
memory: 10948kb

input:

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

output:

-1

result:

ok single line: '-1'

Test #14:

score: 0
Accepted
time: 10ms
memory: 10192kb

input:

1000 2000 1
999 1000
998 1000
997 1000
996 1000
995 1000
994 1000
993 996
992 1000
991 994
990 992
989 996
988 998
987 995
986 990
985 991
984 985
983 987
982 988
981 984
980 988
979 987
978 980
977 981
976 986
975 976
974 983
973 975
972 981
971 972
970 974
969 970
968 972
967 969
966 972
965 968
9...

output:

-1

result:

ok single line: '-1'

Test #15:

score: 0
Accepted
time: 8ms
memory: 9276kb

input:

1000 2000 1
999 1000
998 1000
997 1000
996 1000
995 1000
994 1000
993 1000
992 1000
991 1000
990 1000
989 1000
988 1000
987 1000
986 998
985 1000
984 993
983 1000
982 1000
981 1000
980 988
979 1000
978 1000
977 1000
976 984
975 1000
974 1000
973 1000
972 1000
971 980
970 1000
969 989
968 1000
967 10...

output:

0

result:

ok single line: '0'

Test #16:

score: 0
Accepted
time: 5ms
memory: 10040kb

input:

1000 2000 1
999 1000
998 1000
997 1000
996 997
995 1000
994 998
993 1000
992 1000
991 992
990 992
989 994
988 996
987 993
986 990
985 995
984 991
983 991
982 992
981 982
980 986
979 981
978 984
977 981
976 986
975 979
974 981
973 981
972 982
971 980
970 979
969 972
968 970
967 970
966 975
965 969
96...

output:

165

result:

ok single line: '165'

Test #17:

score: 0
Accepted
time: 14ms
memory: 10344kb

input:

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

output:

74

result:

ok single line: '74'

Test #18:

score: 0
Accepted
time: 7ms
memory: 9380kb

input:

1000 2000 1
1 74
2 21
3 90
4 63
5 100
6 70
7 50
8 108
9 82
10 26
11 74
12 39
13 34
14 25
15 72
16 56
17 50
18 21
19 93
20 85
21 73
22 55
23 85
24 108
25 73
26 67
27 71
28 77
29 126
30 42
31 59
32 75
33 126
34 46
35 101
36 75
37 124
38 94
39 110
40 86
41 132
42 138
43 68
44 53
45 59
46 58
47 93
48 70...

output:

8

result:

ok single line: '8'

Test #19:

score: 0
Accepted
time: 3ms
memory: 10556kb

input:

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

output:

0

result:

ok single line: '0'

Subtask #2:

score: 7
Accepted

Dependency #1:

100%
Accepted

Test #20:

score: 7
Accepted
time: 608ms
memory: 12556kb

input:

1000 200000 1
180 799
43 141
111 439
23 207
84 833
346 930
693 731
3 15
231 879
75 118
63 286
82 988
14 149
786 929
296 474
113 462
771 797
407 497
413 624
12 15
137 249
65 115
208 228
117 141
324 437
246 574
329 410
350 800
444 580
418 964
237 544
173 475
19 39
197 352
480 686
42 884
339 557
370 47...

output:

395

result:

ok single line: '395'

Test #21:

score: 0
Accepted
time: 556ms
memory: 12552kb

input:

1000 200000 1
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 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 ...

output:

286

result:

ok single line: '286'

Test #22:

score: 0
Accepted
time: 551ms
memory: 12500kb

input:

1000 200000 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
15 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
3 54
1 55
1 56
1 57
1 58
1 59
1 6...

output:

196

result:

ok single line: '196'

Test #23:

score: 0
Accepted
time: 598ms
memory: 12632kb

input:

1000 200000 1
999 1000
998 1000
997 1000
996 1000
995 1000
994 1000
993 1000
992 1000
991 1000
990 1000
989 1000
988 1000
987 1000
986 1000
985 1000
984 1000
983 1000
982 1000
981 1000
980 1000
979 1000
978 1000
977 1000
976 1000
975 1000
974 1000
973 1000
972 1000
971 1000
970 1000
969 1000
968 100...

output:

140

result:

ok single line: '140'

Test #24:

score: 0
Accepted
time: 606ms
memory: 253896kb

input:

100000 200000 1
33743 95024
2194 8454
5183 61615
1325 12578
20276 40081
41257 89273
3021 31316
13816 15631
6304 71909
35427 68479
1880 5185
14215 14875
11370 19817
67215 75366
6711 22104
57106 63907
14771 52069
37895 83415
25190 39472
2775 40247
9190 65004
50644 65994
3659 85855
31776 43448
6475 989...

output:

26

result:

ok single line: '26'

Test #25:

score: 0
Accepted
time: 616ms
memory: 265560kb

input:

100000 200000 1
3523 29489
16384 42918
3190 26896
5877 78115
45640 61114
43902 54810
3316 9078
1888 33800
11069 61498
2488 3354
92773 94234
22770 32966
35898 68609
41732 41853
55275 58200
63778 83754
10418 71483
16436 44380
31417 40481
8872 52581
23505 94636
55765 80221
7228 10371
54697 72129
55321 ...

output:

27

result:

ok single line: '27'

Test #26:

score: 0
Accepted
time: 590ms
memory: 264372kb

input:

100000 200000 1
16282 63949
34779 39529
17878 31054
34240 81506
66666 82147
16893 58200
26898 75788
55525 89538
31382 84574
314 27982
16514 16556
16743 78660
6829 10094
2838 28448
23052 38212
15144 19880
4373 16846
4917 41100
2065 3164
26054 44717
24614 89706
6714 8307
12364 42283
2838 15571
8510 27...

output:

-1

result:

ok single line: '-1'

Test #27:

score: 0
Accepted
time: 725ms
memory: 412732kb

input:

100000 200000 1
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 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
5...

output:

55535

result:

ok single line: '55535'

Test #28:

score: 0
Accepted
time: 794ms
memory: 412788kb

input:

100000 200000 1
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 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
5...

output:

59303

result:

ok single line: '59303'

Test #29:

score: 0
Accepted
time: 701ms
memory: 412712kb

input:

100000 200000 1
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 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
5...

output:

31684

result:

ok single line: '31684'

Test #30:

score: 0
Accepted
time: 759ms
memory: 412000kb

input:

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

output:

692

result:

ok single line: '692'

Test #31:

score: 0
Accepted
time: 694ms
memory: 397784kb

input:

100000 200000 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
22 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
46 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
26 59...

output:

152

result:

ok single line: '152'

Test #32:

score: 0
Accepted
time: 792ms
memory: 411988kb

input:

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

output:

-1

result:

ok single line: '-1'

Test #33:

score: 0
Accepted
time: 577ms
memory: 254000kb

input:

100000 200000 1
99999 100000
99998 100000
99997 100000
99996 100000
99995 99998
99994 100000
99993 99996
99992 99995
99991 99993
99990 99994
99989 99990
99988 99996
99987 99990
99986 99994
99985 99987
99984 99992
99983 99989
99982 99984
99981 99982
99980 99983
99979 99980
99978 99988
99977 99980
999...

output:

151

result:

ok single line: '151'

Test #34:

score: 0
Accepted
time: 536ms
memory: 208064kb

input:

100000 200000 1
99999 100000
99998 100000
99997 100000
99996 100000
99995 100000
99994 100000
99993 100000
99992 100000
99991 100000
99990 100000
99989 100000
99988 100000
99987 100000
99986 100000
99985 100000
99984 100000
99983 100000
99982 100000
99981 100000
99980 100000
99979 100000
99978 10000...

output:

60

result:

ok single line: '60'

Test #35:

score: 0
Accepted
time: 586ms
memory: 252384kb

input:

100000 200000 1
99999 100000
99998 100000
99997 100000
99996 100000
99995 99998
99994 100000
99993 100000
99992 99995
99991 99995
99990 99994
99989 99998
99988 99998
99987 99988
99986 99994
99985 99987
99984 99988
99983 99989
99982 99988
99981 99984
99980 99981
99979 99980
99978 99984
99977 99982
99...

output:

0

result:

ok single line: '0'

Test #36:

score: 0
Accepted
time: 763ms
memory: 333280kb

input:

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

output:

5833

result:

ok single line: '5833'

Test #37:

score: 0
Accepted
time: 721ms
memory: 301740kb

input:

100000 200000 1
1 863
2 49
3 587
4 239
5 149
6 834
7 227
8 739
9 31
10 910
11 843
12 909
13 469
14 571
15 915
16 817
17 355
18 399
19 705
20 432
21 798
22 595
23 973
24 288
25 699
26 787
27 510
28 896
29 286
30 765
31 780
32 766
33 743
34 808
35 139
36 38
37 1016
38 803
39 804
40 529
41 750
42 728
4...

output:

61

result:

ok single line: '61'

Test #38:

score: 0
Accepted
time: 732ms
memory: 334164kb

input:

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

output:

-1

result:

ok single line: '-1'

Subtask #3:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Test #39:

score: 0
Wrong Answer
time: 719ms
memory: 256676kb

input:

100000 200000 100000
74040 81077
10075 77192
4167 83961
6357 10091
48911 49972
64254 92040
4703 14723
11456 22053
18940 70698
76356 95132
11150 15058
43813 99395
34762 84775
3889 96199
69856 81771
2216 12369
82025 99321
17607 41771
4008 14665
19596 50414
2519 48648
31365 58806
43855 50597
16875 8209...

output:

0
12
11
19
0
12
1
14
14
21
19
7
20
7
17
17
15
13
18
17
16
0
16
0
16
12
16
14
14
16
20
11
16
24
16
16
0
5
10
16
15
13
19
0
0
13
17
20
21
25
18
16
17
16
14
13
16
16
14
21
1
21
16
16
14
22
18
15
16
14
17
1
16
13
8
17
16
18
16
7
14
0
17
0
17
0
14
23
23
12
14
12
13
16
15
16
1
15
0
0
13
15
11
16
17
22
17
...

result:

wrong answer 2nd lines differ - expected: '21', found: '12'