QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#104695#121. Bitaro's Partylmeowdn14 975ms419116kbC++141.6kb2023-05-11 17:39:412023-05-11 17:39:42

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-11 17:39:42]
  • 评测
  • 测评结果:14
  • 用时:975ms
  • 内存:419116kb
  • [2023-05-11 17:39:41]
  • 提交

answer

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define fi first
#define se second
#define eb emplace_back
#define popc __builtin_popcount
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef unsigned long long ull;
typedef long double ld;

int read() {
  int x=0,w=1; char c=getchar(); 
  while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
  while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();}
  return x*w;
}

const int N=2e5+9,inf=0x3f3f3f3f;
int vst[N],n,m,q,b,del[N],g[N];
vp f[N];
vi e[N];

signed main() {
  n=read(), m=read(), q=read(), b=min(n,300);
  rep(i,1,m) {
    int u=read(), v=read();
    e[v].eb(u);
  }
  rep(i,1,n) {
    vp tmp; f[i].eb(1,i);
    for(int j:e[i]) {
      tmp.resize(f[i].size()+f[j].size());
      merge(f[j].begin(),f[j].end(),
        f[i].begin(),f[i].end(),tmp.begin());
      f[i].clear(); int cnt=0;
      for(auto [w,v]:tmp) {
        if(cnt==b) break;
        if(vst[v]) continue; vst[v]=1;
        f[i].eb(w,v); ++cnt;
      }
      for(auto [w,v]:f[i]) vst[v]=0;
    }
    for(pii &p:f[i]) p.fi--;
  }
  rep(i,1,q) {
    int t=read(), y=read(), ans=-1; vi tmp;
    rep(j,1,y) tmp.eb(read());
    for(int x:tmp) del[x]=1;
    if(y<b) {
      for(auto [w,v]:f[t]) if(!del[v])
        ans=max(ans,-w);
    } else {
      rep(u,1,t) {
        g[u]=(del[u]?-inf:0);
        for(int v:e[u])
          g[u]=max(g[u],g[v]+1);
      }
      ans=max(ans,g[t]);
    }
    printf("%d\n",ans);
    for(int x:tmp) del[x]=0;
  }
  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: 14136kb

input:

1 0 1
1 0

output:

0

result:

ok single line: '0'

Test #2:

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

input:

1 0 1
1 1 1

output:

-1

result:

ok single line: '-1'

Test #3:

score: 0
Accepted
time: 1ms
memory: 13528kb

input:

2 1 1
1 2
1 2 1 2

output:

-1

result:

ok single line: '-1'

Test #4:

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

input:

2 1 1
1 2
1 1 1

output:

-1

result:

ok single line: '-1'

Test #5:

score: 0
Accepted
time: 1ms
memory: 14912kb

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: 4ms
memory: 14828kb

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: 4ms
memory: 14448kb

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: 10ms
memory: 18612kb

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: 5ms
memory: 18376kb

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: 5ms
memory: 18084kb

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: 1ms
memory: 17564kb

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: 1ms
memory: 15588kb

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: 13ms
memory: 16828kb

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: 13ms
memory: 15332kb

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: 2ms
memory: 15140kb

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: 4ms
memory: 16276kb

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: 5ms
memory: 15948kb

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: 4ms
memory: 14632kb

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: 6ms
memory: 16568kb

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: 529ms
memory: 18380kb

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: 484ms
memory: 19556kb

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: 537ms
memory: 17996kb

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: 548ms
memory: 18044kb

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: 623ms
memory: 260448kb

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: 692ms
memory: 272080kb

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: 654ms
memory: 271264kb

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: 653ms
memory: 418580kb

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: 667ms
memory: 418540kb

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: 669ms
memory: 418356kb

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: 672ms
memory: 417524kb

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: 733ms
memory: 403964kb

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: 706ms
memory: 418624kb

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: 481ms
memory: 261120kb

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: 473ms
memory: 214920kb

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: 556ms
memory: 258440kb

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: 582ms
memory: 339304kb

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: 580ms
memory: 307360kb

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: 596ms
memory: 339992kb

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
Time Limit Exceeded

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Test #39:

score: 86
Accepted
time: 717ms
memory: 264284kb

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
21
19
27
0
18
1
24
25
29
29
9
30
7
25
28
23
20
30
26
24
0
26
0
20
20
24
21
25
23
28
18
25
32
24
27
0
5
17
21
22
14
28
0
0
17
28
31
27
34
28
26
26
23
24
19
25
21
18
29
1
33
27
27
26
30
27
26
23
20
26
1
27
16
15
18
23
28
26
7
23
0
26
0
28
0
21
33
32
20
20
17
22
23
25
25
1
23
0
0
17
21
16
27
26
31
28...

result:

ok 100000 lines

Test #40:

score: 0
Accepted
time: 621ms
memory: 267064kb

input:

100000 200000 10000
75227 84466
13112 42732
51738 87607
10577 44557
40520 75357
985 26504
2947 41069
11242 45311
38311 69758
3939 40598
890 9010
9779 12398
38104 71743
982 69579
2772 45919
14027 63915
56066 63588
4247 5707
4323 20659
11957 15738
27348 46564
15885 23455
13449 21976
7225 29377
10955 3...

output:

31
34
29
0
31
28
20
0
35
32
2
38
22
0
34
28
24
36
1
29
1
36
33
0
16
0
28
35
30
25
38
0
23
26
0
24
24
12
23
35
35
29
27
34
25
0
0
18
20
24
29
29
25
0
25
22
34
21
32
29
19
21
0
21
0
14
0
1
29
26
34
0
12
0
31
32
19
26
38
33
0
0
30
25
33
3
33
26
27
37
27
33
34
36
0
1
31
34
21
13
25
24
30
1
22
0
16
0
28
...

result:

ok 10000 lines

Test #41:

score: 0
Accepted
time: 667ms
memory: 270216kb

input:

100000 200000 1000
14602 85035
19668 70385
7089 19409
19241 92558
14080 25682
23541 47432
19558 25894
678 718
391 1212
17560 47791
26199 55408
6748 54557
9230 10026
12163 99200
6207 12650
27849 46133
29203 41554
38084 50025
38454 48718
61518 90511
22423 29561
9247 39096
90714 99594
2912 7853
38287 6...

output:

0
15
32
0
34
3
34
6
38
28
0
0
31
30
25
39
23
31
1
31
31
1
21
23
29
28
0
35
36
0
29
0
29
30
26
35
27
40
16
32
3
37
24
23
24
37
32
29
33
36
32
0
0
26
24
30
27
0
22
25
24
33
21
29
38
16
19
0
37
0
27
28
32
32
14
34
28
30
33
1
22
27
0
0
22
32
26
20
25
20
28
30
38
27
19
29
31
35
28
30
37
29
27
15
1
0
34
3...

result:

ok 1000 lines

Test #42:

score: 0
Accepted
time: 680ms
memory: 267660kb

input:

100000 200000 100
79457 88426
9896 35927
27255 45300
34295 51312
13924 69539
28276 81895
14529 26843
20957 51320
81777 98717
17321 53247
10723 77381
2484 5243
32373 44565
18277 31410
31782 39053
56619 62084
28950 44417
9914 39664
44400 57264
820 1162
11551 85834
22357 29656
28654 32720
10829 88257
2...

output:

25
30
35
31
36
35
32
27
33
1
28
28
27
0
30
0
27
1
17
17
29
36
1
27
0
20
30
28
34
35
27
30
32
35
33
3
22
33
31
23
28
27
39
10
0
24
0
5
27
28
29
28
21
32
2
34
31
18
23
0
28
18
40
35
31
28
24
2
35
36
28
34
0
22
19
29
24
2
1
23
33
25
32
25
33
27
33
25
23
30
0
33
34
30
32
28
36
27
1
0

result:

ok 100 lines

Test #43:

score: 0
Accepted
time: 742ms
memory: 337812kb

input:

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

output:

5513
284
270
14765
0
5780
3280
3266
16824
2306
5218
1470
7166
6363
6562
15096
6970
0
921
350
281
8393
8670
1473
6886
17567
1264
1
8919
10003
17165
2602
6748
2925
10057
2039
3
353
275
0
13134
142
2
12437
9186
1021
6567
15173
1476
3950
760
7297
17894
1983
1566
3905
13025
3037
0
10220
694
13105
1394
27...

result:

ok 300 lines

Test #44:

score: 0
Accepted
time: 747ms
memory: 309324kb

input:

100000 200000 300
1 22
2 57
3 858
4 896
5 453
6 170
7 650
8 394
9 481
10 30
11 610
12 510
13 291
14 379
15 883
16 715
17 924
18 127
19 26
20 464
21 27
22 703
23 151
24 904
25 662
26 803
27 517
28 514
29 789
30 151
31 62
32 220
33 971
34 160
35 53
36 723
37 793
38 198
39 698
40 436
41 372
42 1011
43 ...

output:

6
62
91
64
2
95
82
2
12
82
195
0
202
75
0
0
22
64
27
41
27
91
31
7
129
30
54
181
0
1
3
154
12
4
28
0
0
0
148
23
13
52
94
0
164
19
0
73
31
0
90
29
10
0
176
35
114
26
6
2
0
100
99
0
44
6
10
44
13
20
124
17
3
43
178
197
85
0
21
68
12
19
0
16
116
28
1
0
85
195
31
42
117
56
82
7
24
101
0
47
86
7
117
34
6...

result:

ok 300 lines

Test #45:

score: 0
Accepted
time: 658ms
memory: 417868kb

input:

100000 200000 500
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...

output:

3708
76706
72230
19926
14998
5639
56267
73846
47900
88791
33947
61077
56261
95673
13400
12377
3573
41032
94807
68894
56165
31026
62804
15311
46722
86128
11233
96370
41975
82074
67518
82079
28245
19071
51328
74428
25937
6850
32503
50932
80113
51519
78596
30841
58737
31324
30031
85216
8365
23926
19494...

result:

ok 500 lines

Test #46:

score: 0
Accepted
time: 740ms
memory: 340768kb

input:

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

output:

0
0
825
696
2293
0
2055
0
4133
0
893
0
9273
1526
112
17668
0
10144
4513
3495
13591
8362
2648
8970
1255
4494
2
181
350
7543
0
2212
1247
0
4452
6680
6483
9562
17579
11844
0
3777
1381
4400
0
11793
3230
246
0
5497
13418
9249
9108
0
5745
0
329
4172
8032
6614
14339
4623
9976
688
10664
3182
3152
1006
5863
...

result:

ok 500 lines

Test #47:

score: 0
Accepted
time: 584ms
memory: 305208kb

input:

100000 200000 500
1 874
2 909
3 998
4 648
5 573
6 78
7 798
8 266
9 705
10 14
11 466
12 241
13 94
14 172
15 998
16 796
17 169
18 560
19 411
20 975
21 499
22 268
23 763
24 752
25 949
26 611
27 229
28 842
29 91
30 261
31 537
32 677
33 818
34 740
35 448
36 697
37 448
38 389
39 961
40 895
41 61
42 453
43...

output:

31
31
22
113
66
7
71
1
67
105
56
8
45
47
50
2
29
0
135
168
64
9
0
19
42
28
41
113
224
22
96
6
117
155
17
0
0
19
0
25
141
77
6
148
51
199
101
109
5
0
53
126
104
182
10
38
146
57
88
10
201
140
76
1
97
0
25
2
31
51
8
122
18
53
121
75
73
24
15
17
105
23
34
0
48
1
27
7
0
9
6
114
137
32
1
6
45
5
0
55
160
...

result:

ok 500 lines

Test #48:

score: 0
Accepted
time: 683ms
memory: 419116kb

input:

100000 200000 10
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
...

output:

76929
29960
56738
49737
7270
63950
5643
2493
77841
49603

result:

ok 10 lines

Test #49:

score: 0
Accepted
time: 614ms
memory: 339612kb

input:

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

output:

-1
3426
289
-1
2379
9226
4
8268
5716
12090

result:

ok 10 lines

Test #50:

score: 0
Accepted
time: 597ms
memory: 308472kb

input:

100000 200000 10
1 743
2 337
3 155
4 816
5 748
6 442
7 371
8 586
9 545
10 14
11 891
12 120
13 797
14 109
15 40
16 201
17 421
18 73
19 98
20 198
21 267
22 33
23 310
24 584
25 586
26 35
27 373
28 1026
29 79
30 975
31 665
32 346
33 666
34 638
35 148
36 1017
37 332
38 212
39 526
40 954
41 1014
42 682
43...

output:

0
0
58
31
2
0
96
1
156
0

result:

ok 10 lines

Test #51:

score: 0
Accepted
time: 711ms
memory: 418404kb

input:

100000 200000 30
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
...

output:

78376
5816
32044
33906
67875
92396
17899
93286
4150
91062
89678
81473
30571
17891
2343
64120
15508
83194
48012
53357
86796
92995
90443
42156
52487
89957
36816
69825
18029
35139

result:

ok 30 lines

Test #52:

score: 0
Accepted
time: 603ms
memory: 340408kb

input:

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

output:

0
6186
16045
-1
4275
14241
771
116
4156
9467
5597
4516
13187
3
6096
15481
0
0
5529
2955
1733
1033
8757
5454
5858
2038
10324
6860
17362
2

result:

ok 30 lines

Test #53:

score: 0
Accepted
time: 609ms
memory: 308068kb

input:

100000 200000 30
1 595
2 189
3 295
4 568
5 868
6 350
7 519
8 458
9 769
10 998
11 747
12 851
13 600
14 902
15 157
16 50
17 88
18 610
19 483
20 149
21 739
22 870
23 922
24 712
25 73
26 347
27 85
28 522
29 633
30 949
31 86
32 631
33 579
34 466
35 305
36 723
37 933
38 995
39 285
40 509
41 207
42 112
43 ...

output:

2
-1
184
195
-1
52
160
125
140
1
32
0
106
101
16
102
36
110
18
77
51
7
122
0
100
19
25
83
7
28

result:

ok 30 lines

Test #54:

score: 0
Accepted
time: 779ms
memory: 418704kb

input:

100000 200000 100000
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...

output:

7352
11279
85655
20877
59893
25404
78763
75369
67558
82423
73581
5302
18223
15789
35031
35606
80710
28908
54134
66918
35779
53621
84798
85436
51123
78440
43381
38847
86451
80157
96510
24019
94178
63968
71345
73251
60325
54725
20565
70430
18460
92502
61348
41749
27717
93291
30440
65345
39226
24074
90...

result:

ok 100000 lines

Test #55:

score: 0
Accepted
time: 646ms
memory: 417668kb

input:

100000 200000 1000
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 5...

output:

27691
71213
91210
75729
34927
36696
96418
16688
85900
62964
24859
7534
66658
74539
36772
91870
1257
45412
98894
96121
1709
23519
90084
67234
5333
29059
21941
89472
9183
34856
93508
11639
17640
72467
16306
74624
37452
32076
10627
77212
82710
31621
71644
72725
28809
28850
93524
34278
33054
94476
67153...

result:

ok 1000 lines

Test #56:

score: 0
Accepted
time: 663ms
memory: 418140kb

input:

100000 200000 10
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
...

output:

57693
6408
21900
88802
63585
27734
14155
4478
83502
49353

result:

ok 10 lines

Test #57:

score: 0
Accepted
time: 571ms
memory: 18732kb

input:

1000 200000 100000
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 5...

output:

397
881
361
311
701
806
967
650
621
775
434
230
729
130
897
632
781
240
817
413
940
549
345
398
486
36
171
500
23
166
653
278
209
790
145
310
714
422
371
780
889
725
419
91
69
327
404
149
666
10
853
579
861
278
829
783
641
79
553
618
951
920
23
662
992
139
936
57
20
932
72
894
625
767
15
151
543
680...

result:

ok 100000 lines

Test #58:

score: 0
Accepted
time: 485ms
memory: 17800kb

input:

1000 200000 1000
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
...

output:

568
323
429
158
990
890
824
554
901
319
65
679
471
191
528
169
675
255
25
904
6
63
650
374
44
695
952
908
909
318
838
788
154
624
532
535
204
498
547
463
943
66
278
557
141
852
572
762
248
473
915
64
799
274
844
598
66
671
676
721
950
841
106
595
300
442
291
503
590
299
813
692
185
824
746
595
435
3...

result:

ok 1000 lines

Test #59:

score: 0
Accepted
time: 485ms
memory: 17548kb

input:

1000 200000 10
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:

785
587
105
658
449
288
374
731
795
429

result:

ok 10 lines

Test #60:

score: 0
Accepted
time: 773ms
memory: 416956kb

input:

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

output:

9528
12174
11496
3672
2673
7633
13642
2521
11569
15166
8251
6190
7638
2341
11768
17672
4037
2527
9937
8018
5084
13295
17639
13220
9297
16701
3028
6774
2358
4086
16466
112
14916
11629
15237
2115
15756
16601
4178
16855
10213
488
16191
1420
7657
3463
2670
18112
12552
10642
8437
5510
1514
10980
9524
166...

result:

ok 100000 lines

Test #61:

score: 0
Accepted
time: 975ms
memory: 402828kb

input:

100000 200000 100000
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
20 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
1 54
1 55
1 56
1 57
1 58
1...

output:

34
110
83
203
186
174
50
105
218
26
191
216
196
119
223
201
165
206
91
137
78
201
197
117
52
140
211
204
148
207
185
67
173
91
103
105
38
214
14
227
203
46
51
26
179
17
45
188
109
206
46
206
209
137
29
148
171
67
184
85
146
131
226
100
114
200
208
18
36
74
91
57
129
179
204
87
94
87
38
228
148
79
47...

result:

ok 100000 lines

Test #62:

score: -86
Time Limit Exceeded

input:

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

output:

3155
5897
13111
7919
4245
1445
9851
2081
12741
137
10305
15762
17120
1080
16987
18235
6873
11692
2995
3651
1136
13953
3059
12678
3594
6842
3950
9740
6118
15587
2840
12630
1952
18251
9539
10346
7577
5966
16395
7250
9402
1182
3175
5685
10903
9636
12710
5714
3481
244
1727
3603
17493
5575
9919
14225
138...

result: