QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#763403#6332. Two Currenciescocoa_chan10 3720ms130356kbC++144.0kb2024-11-19 20:05:102024-11-19 20:05:10

Judging History

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

  • [2024-11-19 20:05:10]
  • 评测
  • 测评结果:10
  • 用时:3720ms
  • 内存:130356kb
  • [2024-11-19 20:05:10]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll siz=262144;
ll n,m,i,j,k,l,r,x,y,z,w,s,t,a[1100000],le[1100000],ri[1100000],seg[3][1100000],silver[1100000],gold[1100000],ednum[1100000],stnum[1100000],st[1100000],ed[1100000],h[1100000],b[1100000],q,sparse[21][110000],ee,mid;
vector<ll> v[1100000];
vector<ll> u[1100000];
pair<ll,ll> p[1100000],pp[1100000];
void dfs(ll x,ll y)
{
    sparse[0][x]=y;
    h[x]=h[y]+1;
    t++;
    stnum[x]=t;
    ll i;
    for(i=0;i<v[x].size();i++)
    {
        if(v[x][i]==y)
            continue;
        dfs(v[x][i],x);
    }
    t++;
    ednum[x]=t;
}
void Clear()
{
    ll i;
    for(i=0;i<550000;i++)
    {
        seg[1][i]=0;
        seg[2][i]=0;
    }
}
void f(ll idx,ll z)
{
    seg[idx][z]=seg[idx][z*2]+seg[idx][z*2+1];
    if(z==1)
        return;
    f(idx,z/2);
}
ll g(ll idx,ll x,ll y,ll z)
{
    if(l>y||x>r)
        return 0;
        if(l<=x&&y<=r)
            return seg[idx][z];
    return g(idx,x,(x+y)/2,z*2)+g(idx,(x+y)/2+1,y,z*2+1);
}
void add(ll idx,ll x,ll y,ll z)
{
    if(h[x]>h[y])
        swap(x,y);
    seg[idx][stnum[y]+siz-1]+=z;
    f(idx,(stnum[y]+siz-1)/2);
    seg[idx][ednum[y]+siz]-=z;
    f(idx,(ednum[y]+siz)/2);
}
ll lca(ll x,ll y)
{
    if(h[x]>h[y])
        swap(x,y);
    ll w=h[y]-h[x],z=0;
    while(w)
    {
        if(w&1)
        {
            y=sparse[z][y];
        }
        w>>=1;
        z++;
    }
    if(x==y)
        return x;
    z=18;
    while(z>=0)
    {
        if(sparse[z][x]!=sparse[z][y])
        {
            x=sparse[z][x];
            y=sparse[z][y];
        }
        z--;
    }
    return sparse[0][x];
}
ll query(ll idx,ll x,ll y)
{
    if(h[x]<h[y])
        swap(x,y);

    ll z=lca(x,y);
    //printf("(%lld,%lld,%lld)\n",x,y,z);
    ll s=0;
    l=1;
    r=stnum[x];
    s+=g(idx,1,siz,1);
    //printf("(%lld)",s);
    l=1;
    r=stnum[y];
    s+=g(idx,1,siz,1);
    //printf("(%lld)",s);
    l=1;
    r=stnum[z];
    s-=2*g(idx,1,siz,1);
    //printf("(%lld)",s);
    return s;
}
int main()
{
    scanf("%lld %lld %lld",&n,&m,&q);
    for(i=1;i<n;i++)
    {
        scanf("%lld %lld",&x,&y);
        p[i]={x,y};
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1,0);
    for(j=1;j<=20;j++)
    {
        for(i=1;i<=n;i++)
        {
            sparse[j][i]=sparse[j-1][sparse[j-1][i]];
        }
    }
    for(i=1;i<=m;i++)
    {
        scanf("%lld %lld",&x,&y);
        pp[i]={y,x};
    }
    sort(pp+1,pp+m+1);
    for(i=1;i<=m;i++)
        swap(pp[i].first,pp[i].second);
    for(i=1;i<=q;i++)
    {
        scanf("%lld %lld %lld %lld",&x,&y,&z,&w);
        le[i]=0;
        ri[i]=m;
        st[i]=x;
        ed[i]=y;
        gold[i]=z;
        silver[i]=w;
    }
    for(ee=0;ee<18;ee++)
    {
        //printf("!");
        Clear();
        for(i=1;i<=m;i++)
        {
            add(1,p[pp[i].first].first,p[pp[i].first].second,1);
        }
        for(i=0;i<=m+1;i++)
        {
            u[i].clear();
        }
        for(i=1;i<=q;i++)
        {
            mid=(le[i]+ri[i]+1)/2;
            u[mid].push_back(i);
        }
        for(i=0;i<=m;i++)
        {
            if(i)
            {
                add(2,p[pp[i].first].first,p[pp[i].first].second,pp[i].second);
                add(1,p[pp[i].first].first,p[pp[i].first].second,-1);
            }
            for(auto xx:u[i])
            {
                x=st[xx];
                y=ed[xx];
                b[xx]=query(1,x,y);
                s=query(2,x,y);
                //printf("(%lld,%lld,%lld:%lld)\n",i,x,y,s);
                if(silver[xx]<s)
                {
                    ri[xx]=i-1;
                }
                else
                {le[xx]=i;
                }
            }
        }
    }
    for(i=1;i<=q;i++)
    {
        if(gold[i]-b[i]<0)
            printf("-1\n");
        else
        printf("%lld\n",gold[i]-b[i]);
    }
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 42ms
memory: 88720kb

input:

1831 1865 1153
832 1698
1672 1619
634 920
328 1244
571 1279
1673 1815
1098 92
1320 432
244 636
991 1446
308 569
1118 1356
1733 71
497 1679
1699 635
1254 1295
853 345
364 1396
1183 1134
524 1557
1642 1262
1767 459
918 794
1644 539
902 1046
334 1789
1691 1548
1298 520
1763 216
1161 1065
682 1167
1282 ...

output:

378730605
649537044
339843141
362013697
600127619
123276007
749019778
22
30
54569538
-1
26669081
33
255375699
0
7
8
-1
427653834
2
9
19
7
9
-1
8
6
265022184
218253041
-1
24
849614439
9
29092527
539604026
0
6
-1
6
-1
12
8
-1
22
-1
13
11
26
7
-1
2
0
546008661
4
6
86261072
-1
448122840
873577464
-1
0
1...

result:

ok 1153 numbers

Test #2:

score: 10
Accepted
time: 53ms
memory: 74800kb

input:

1942 1832 1894
1076 1725
1111 725
1093 19
921 1759
1917 1017
1854 724
901 1713
58 1482
1469 134
1463 1030
159 162
3 570
781 1533
64 1043
1693 894
329 1075
252 1727
1579 213
1051 419
67 80
351 1739
990 313
1545 94
680 649
1769 140
678 1755
602 17
598 476
586 509
1321 1535
402 949
1135 1196
1668 985
1...

output:

290930763
222025343
905421625
3
2
691499099
9
-1
-1
923482030
11
11
22
10
1
5
12
13
230762895
808118430
470508163
-1
-1
5
769521091
1
649347743
867764525
3
4
9
-1
635895869
518880732
-1
161787337
812530072
-1
7
8
25
-1
5
6
0
3
655886721
576512193
3
440416008
7
8
-1
-1
-1
11
11
3
-1
418197782
5773691...

result:

ok 1894 numbers

Test #3:

score: 10
Accepted
time: 46ms
memory: 90620kb

input:

1259 1420 1830
767 33
409 881
144 630
754 665
98 954
1133 741
163 1011
351 474
1165 168
213 70
1257 801
654 727
336 1238
147 756
956 639
540 671
1049 837
967 768
275 565
480 791
922 739
504 906
281 683
1069 1019
1195 716
851 45
119 515
1226 997
153 1163
1180 333
941 649
32 1199
1118 699
144 181
675 ...

output:

20
293315087
17
214464390
1
7
1
1
463782411
193462252
-1
264243615
238908207
-1
578800563
1
17
20
2
-1
490218156
4
2587714
12
17716886
171554130
22
10
10
283890617
3
32583568
1
1
3
334255184
7
6
2
3
518826413
610186572
-1
3
297569392
-1
-1
0
-1
4
987836934
0
35
315447009
10
13
14
-1
-1
711900410
19
...

result:

ok 1830 numbers

Test #4:

score: 10
Accepted
time: 53ms
memory: 90832kb

input:

2000 2000 2000
439 1912
92 340
1771 416
403 550
885 1093
1664 1308
124 506
1535 1848
1806 1245
1057 791
805 1930
1607 1456
1795 1409
969 1527
471 1553
1794 1721
1967 829
979 243
1360 295
392 911
963 1566
1815 663
356 770
23 924
964 1883
1668 1499
1514 927
412 1764
1270 418
649 369
1828 1958
687 428
...

output:

16
18
6
-1
7
-1
14
0
17
10
8
16
4
-1
11
9
6
7
9
27
0
17
1
-1
22
29
-1
-1
-1
5
0
3
-1
-1
4
22
4
1
5
7
15
8
14
-1
7
11
9
1
12
17
-1
10
15
5
17
-1
1
1
18
-1
13
7
-1
4
18
2
13
-1
-1
5
13
3
5
-1
13
0
13
5
5
4
-1
22
11
-1
6
20
10
9
-1
-1
2
24
1
-1
0
3
1
4
-1
2
-1
14
15
6
-1
9
17
3
4
4
10
11
-1
2
9
-1
-1
1...

result:

ok 2000 numbers

Test #5:

score: 10
Accepted
time: 52ms
memory: 90792kb

input:

2000 2000 2000
1908 583
1115 1046
1858 74
587 1569
549 1911
1350 1887
1101 277
396 1518
569 1528
988 150
1559 1967
683 484
1569 1050
1864 1335
1218 52
1600 925
1047 90
1870 1263
157 185
141 1388
316 102
1903 1907
124 1179
1172 1928
1730 1398
1226 1976
450 657
1830 821
275 459
1382 634
1458 297
1212 ...

output:

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

result:

ok 2000 numbers

Test #6:

score: 10
Accepted
time: 51ms
memory: 72700kb

input:

2000 2000 2000
1532 700
306 1701
1697 1130
2000 1322
661 231
77 683
1773 1224
634 1533
155 1831
1418 1618
1945 1255
607 1006
432 20
298 1250
1180 1430
1796 142
144 1379
1713 583
1583 80
1552 1280
1327 1705
1861 517
337 725
669 303
1974 628
1176 829
1258 251
172 1757
1737 1486
1585 597
1440 1552
1610...

output:

1
20
-1
-1
-1
7
0
0
-1
13
7
6
2
-1
5
6
8
-1
1
7
11
-1
-1
-1
6
8
-1
-1
2
-1
6
10
10
-1
16
16
-1
-1
0
8
-1
-1
12
15
8
10
1
23
7
9
6
3
14
8
0
5
7
3
8
12
-1
10
1
4
-1
24
-1
22
-1
0
10
0
-1
1
23
2
2
-1
1
13
3
4
5
-1
14
4
7
-1
2
11
9
13
15
9
4
-1
7
6
3
16
1
0
7
5
11
1
32
3
26
-1
-1
8
11
3
4
2
13
9
10
-1
2...

result:

ok 2000 numbers

Test #7:

score: 10
Accepted
time: 54ms
memory: 72832kb

input:

2000 2000 2000
241 900
1930 1379
1438 670
667 1290
733 1932
1295 1721
855 1330
850 601
1751 716
1081 1571
1983 717
1269 1751
1288 69
333 714
1202 600
1447 576
1745 383
151 1669
1565 1814
689 1870
648 1217
1529 1190
957 1840
1130 1713
1660 558
102 1316
1784 973
1057 1072
113 1883
766 1033
182 326
121...

output:

7
11
31
-1
28
25
25
7
4
-1
-1
-1
-1
19
-1
9
2
0
7
13
1
17
4
4
59
17
2
8
36
0
0
10
2
-1
9
14
13
2
1
-1
11
7
-1
-1
3
0
18
-1
0
8
1
29
24
15
6
13
29
10
15
3
3
6
3
43
-1
1
-1
-1
5
17
-1
3
5
14
10
12
16
4
15
7
9
18
0
14
6
11
-1
9
15
-1
-1
21
0
20
15
11
14
18
32
-1
13
6
-1
-1
23
11
-1
13
-1
6
5
-1
12
7
1
...

result:

ok 2000 numbers

Test #8:

score: 10
Accepted
time: 62ms
memory: 66716kb

input:

2000 2000 2000
1453 1310
1106 1265
57 520
1265 300
461 1199
1805 139
62 628
1923 1503
703 1334
10 141
942 1165
1850 983
475 1937
1821 954
1771 752
825 1914
1534 944
452 1551
1532 1010
724 1212
323 1637
1159 65
312 621
1633 581
1096 1964
889 1083
857 1590
1367 1329
30 36
286 507
174 1681
413 840
592 ...

output:

4
-1
-1
-1
9
14
5
6
22
-1
-1
34
20
-1
35
0
16
9
7
14
-1
9
13
0
18
6
5
-1
5
15
6
2
18
5
18
8
7
10
13
12
20
10
-1
-1
2
9
2
-1
-1
2
6
29
11
27
10
2
4
3
22
7
1
9
20
11
1
-1
2
8
16
13
-1
-1
8
21
5
-1
0
14
-1
9
9
5
21
3
8
13
24
-1
13
12
2
-1
18
27
3
9
-1
10
12
-1
9
-1
-1
4
-1
10
12
8
11
-1
6
5
5
7
15
0
-1...

result:

ok 2000 numbers

Test #9:

score: 10
Accepted
time: 50ms
memory: 66764kb

input:

2000 2000 2000
322 586
1516 535
436 1706
471 1457
1013 1890
787 511
1276 49
43 1558
1869 822
1599 1671
1139 1791
1385 720
522 524
1537 1720
1641 570
1987 1657
1244 1000
266 1703
1987 1586
134 89
1226 1343
1316 823
1505 890
123 662
1154 607
1349 1847
1379 1072
1483 414
97 1549
861 869
1807 169
794 82...

output:

1710
220
-1
447
10
1456
480
78
411
-1
81
274
-1
-1
184
1889
73
-1
-1
-1
45
-1
184
697
251
555
149
27
20
503
213
181
490
1290
156
108
-1
-1
138
512
128
1013
378
968
-1
52
764
404
274
-1
119
2178
-1
-1
1667
-1
845
235
1358
37
201
-1
-1
1199
1504
-1
309
1040
1438
-1
80
-1
-1
1346
-1
352
683
1017
-1
12
...

result:

ok 2000 numbers

Test #10:

score: 10
Accepted
time: 51ms
memory: 72780kb

input:

2000 2000 2000
1564 687
910 825
141 1628
1559 423
968 936
621 1039
313 1740
910 23
1665 1510
807 1509
218 992
1668 37
250 1361
1924 1002
1031 406
177 86
1250 1886
1904 534
801 524
1902 484
1527 520
1210 115
652 1086
1413 239
1223 966
1985 165
760 554
1357 751
1232 913
513 1189
1433 474
480 1782
464 ...

output:

1360
-1
69
320
398
486
853
300
579
600
956
1447
142
83
115
305
53
864
83
24
447
190
-1
1212
36
128
155
-1
-1
245
388
-1
-1
1215
38
37
3
3
805
610
70
-1
380
146
157
87
-1
1057
1525
-1
423
559
5
204
517
723
63
1442
70
110
441
15
1116
-1
-1
203
-1
1044
-1
89
119
524
1080
1648
213
395
344
1095
788
164
8...

result:

ok 2000 numbers

Test #11:

score: 10
Accepted
time: 51ms
memory: 66728kb

input:

2000 2000 2000
1509 92
1257 1098
1768 1647
359 654
1743 1459
968 1397
1010 58
1725 70
1808 22
1262 1492
118 191
1455 618
827 1723
1775 246
14 824
325 1660
1821 1246
855 246
1189 1011
926 310
782 811
190 8
1949 1001
1210 1383
884 23
408 1294
221 312
1056 1294
1731 1698
1521 1069
248 1514
1747 153
152...

output:

-1
262
251
-1
18
164
268
-1
27
246
50
120
331
65
-1
49
321
512
7
14
227
151
110
0
343
1
68
188
196
-1
-1
164
110
134
241
379
39
473
16
155
58
454
29
-1
-1
621
126
392
8
-1
364
539
595
507
188
-1
174
337
-1
526
493
323
162
104
-1
256
220
-1
257
307
146
494
-1
256
65
10
170
-1
-1
142
39
34
459
158
490...

result:

ok 2000 numbers

Test #12:

score: 10
Accepted
time: 47ms
memory: 72620kb

input:

2000 2000 2000
598 1485
5 1107
1741 985
819 1339
126 1615
712 725
121 1355
821 1194
1924 1438
175 70
1846 1508
216 741
1624 1154
891 394
1993 45
1878 269
1931 1443
385 669
576 1307
1823 1002
1349 1641
808 1086
397 1906
508 1910
122 1973
1913 972
291 900
1865 88
553 202
854 1437
482 554
1398 868
347 ...

output:

300
208
34
35
259
65
-1
76
32
333
362
250
12
-1
75
335
-1
12
-1
468
-1
-1
-1
11
123
193
-1
523
79
133
139
456
-1
366
-1
362
-1
81
357
140
115
452
4
104
-1
78
160
110
376
52
120
231
336
329
359
-1
94
-1
19
-1
50
119
-1
67
183
135
124
90
352
82
359
-1
370
667
103
28
207
50
132
279
-1
-1
68
355
275
147...

result:

ok 2000 numbers

Test #13:

score: 10
Accepted
time: 47ms
memory: 66788kb

input:

2000 2000 2000
1057 1968
457 468
920 715
56 1653
1457 229
581 1751
1289 1738
268 403
1254 1996
1878 1456
1891 250
200 1729
651 1667
1870 1125
596 1287
1166 556
1783 1201
837 703
426 1523
1730 1151
1154 564
892 1273
1068 440
1481 248
241 1861
704 1556
720 1960
91 1535
75 221
1436 1561
1133 965
468 15...

output:

174
243
113
81
488
81
54
20
37
121
-1
108
39
51
-1
77
163
234
185
38
176
43
3
104
96
167
158
18
22
-1
13
-1
-1
101
-1
31
82
9
0
220
197
155
-1
83
32
48
248
144
36
200
240
241
3
-1
47
62
196
17
-1
80
176
40
-1
26
192
100
199
19
8
-1
78
-1
514
141
9
-1
5
138
-1
129
209
-1
-1
325
-1
-1
247
170
383
66
6...

result:

ok 2000 numbers

Test #14:

score: 10
Accepted
time: 51ms
memory: 72792kb

input:

2000 2000 2000
817 926
1659 1203
1736 806
1653 705
1801 1424
476 698
115 392
269 96
391 1094
419 1683
1079 1216
1080 1378
1846 492
837 871
1237 498
1307 1367
929 734
1149 1000
721 118
757 567
843 985
665 1662
1422 1418
79 1326
28 801
1 254
1821 1901
1737 747
726 292
1607 52
1321 1049
943 1543
1527 7...

output:

-1
-1
57
35
2
-1
298
-1
-1
320
408
95
45
-1
42
463
578
-1
39
423
290
-1
184
105
235
-1
-1
311
-1
663
270
0
518
7
66
471
107
307
166
633
168
190
136
-1
174
-1
330
59
324
-1
199
-1
356
61
155
510
107
702
-1
-1
-1
-1
54
174
407
75
144
461
-1
96
-1
513
66
-1
187
-1
-1
139
54
499
-1
611
-1
-1
243
504
-1
...

result:

ok 2000 numbers

Test #15:

score: 10
Accepted
time: 68ms
memory: 90844kb

input:

2000 2000 2000
1681 700
1949 700
1904 700
700 1715
700 46
1 700
700 870
1044 700
700 586
700 766
731 700
700 720
700 313
700 1064
1459 700
189 700
700 1063
700 113
891 700
700 141
700 1073
700 510
700 989
700 683
700 1328
1513 700
1096 700
618 700
700 509
919 700
196 700
700 1672
700 1763
1733 700
9...

output:

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

result:

ok 2000 numbers

Test #16:

score: 10
Accepted
time: 56ms
memory: 78824kb

input:

2000 2000 2000
1523 891
1530 891
891 1477
1199 891
891 1499
891 326
1043 891
1629 891
891 1686
891 1334
891 795
1483 891
1618 891
1243 891
1482 891
891 606
96 891
891 1904
1750 891
401 891
891 1456
891 859
769 891
891 1663
891 70
891 161
891 559
891 217
891 571
1699 891
891 250
1655 891
1648 891
184...

output:

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

result:

ok 2000 numbers

Test #17:

score: 10
Accepted
time: 46ms
memory: 104976kb

input:

2000 2000 2000
1284 391
1284 555
1284 1509
1577 1284
763 1284
1284 332
1284 570
1284 1101
1761 1284
1759 1284
1529 1284
1284 1466
4 1284
1284 744
142 1284
1765 1284
1015 1284
1284 1189
1747 1284
1386 1284
1284 606
124 1284
1284 768
1020 1284
1284 379
1284 1914
1652 1284
129 1284
1032 1284
1284 70
12...

output:

0
1
0
-1
1
1
1
1
0
0
1
3
1
3
1
4
0
0
-1
0
3
1
1
0
0
0
1
-1
0
1
0
1
2
3
0
1
-1
0
2
1
-1
0
0
5
4
0
0
2
-1
5
5
2
0
0
3
6
3
1
0
-1
5
0
-1
3
0
0
3
2
2
3
3
0
1
-1
0
-1
0
0
0
1
-1
4
2
4
2
0
1
-1
4
0
0
0
1
0
2
1
0
0
2
4
0
1
0
0
-1
-1
1
8
3
3
1
-1
4
3
2
2
2
1
0
-1
11
0
1
0
1
-1
3
2
3
0
-1
0
-1
1
1
-1
0
1
0
-...

result:

ok 2000 numbers

Test #18:

score: 10
Accepted
time: 56ms
memory: 105348kb

input:

2000 2000 2000
1197 238
814 238
1746 238
321 238
238 797
776 238
238 109
238 285
724 238
238 149
238 1737
238 249
238 473
238 420
699 238
779 238
304 238
889 238
238 1626
238 923
238 1810
1120 238
1463 238
437 238
238 1779
238 929
238 949
238 1483
223 238
1544 238
238 981
1978 238
293 238
494 238
17...

output:

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

result:

ok 2000 numbers

Test #19:

score: 10
Accepted
time: 44ms
memory: 104572kb

input:

2000 2000 2000
23 1970
854 76
1538 706
612 807
900 1523
258 1046
738 1821
541 931
762 1406
1205 1080
1006 211
810 1190
39 1727
397 850
572 569
1447 1745
1057 1400
1459 696
1822 1309
1703 1833
1611 683
1362 579
1426 63
261 271
1418 1587
814 309
224 1327
1166 1239
113 1581
14 895
1098 267
368 1340
163...

output:

1528
-1
3
-1
491
5
1291
929
1412
1161
2
9
-1
-1
-1
4
842
-1
578
1385
4
-1
-1
6
1629
-1
-1
9
183
4
7
0
-1
280
-1
677
-1
922
1156
775
-1
-1
11
9
1573
200
-1
1698
452
611
1
-1
737
1104
9
-1
4
542
10
-1
3
1
488
380
-1
13
5
-1
1434
798
543
589
4
-1
-1
1
6
7
-1
-1
-1
523
5
-1
1756
801
1
372
1101
1593
3
10...

result:

ok 2000 numbers

Test #20:

score: 10
Accepted
time: 47ms
memory: 103860kb

input:

2000 2000 2000
123 1636
53 1142
1587 1681
1871 481
959 634
1162 342
815 1745
663 794
122 863
1809 581
179 1822
26 1072
478 513
564 1116
1751 383
834 222
1805 5
1483 1517
1283 833
1191 209
621 780
1665 1047
205 14
1826 480
170 203
1095 1276
542 470
750 1760
539 573
1728 219
1756 1898
906 1616
884 190...

output:

0
1
3
3
0
-1
-1
1507
709
878
1
-1
-1
6
-1
5
10
10
0
16
-1
1798
-1
3
-1
7
1142
3
-1
-1
7
2
1
405
0
-1
3
1257
10
-1
54
-1
-1
3
488
6
1243
-1
-1
-1
2
964
4
988
-1
1309
1379
3
2
1810
2
2
27
188
0
-1
-1
1293
494
559
1
475
511
5
-1
6
3
-1
663
9
-1
1185
7
6
-1
232
3
-1
-1
-1
406
-1
1
-1
6
1
3
492
76
3
-1
4...

result:

ok 2000 numbers

Test #21:

score: 10
Accepted
time: 45ms
memory: 103220kb

input:

2000 2000 2000
799 1750
150 482
1299 1970
1106 1409
1392 167
324 693
584 555
1703 1440
62 1001
1681 1652
145 371
1019 1842
1041 512
1263 81
1816 435
7 1470
1301 857
1506 1742
1759 1891
1245 1968
616 913
1653 1282
1014 143
1501 1753
1248 1444
875 1668
1382 1426
132 1260
264 1707
497 1124
1073 1926
56...

output:

0
-1
-1
1
482
6
4
0
386
4
2
652
0
4
160
0
-1
-1
3
0
758
900
1
-1
488
-1
-1
-1
845
-1
221
-1
-1
-1
-1
5
1311
6
-1
3
1074
1086
-1
1
-1
1359
5
95
-1
-1
-1
5
0
540
228
1
820
7
646
-1
207
-1
1604
-1
-1
2
-1
-1
15
1
1031
-1
-1
222
6
-1
-1
2
-1
-1
0
5
-1
1339
-1
-1
-1
1162
462
5
97
68
5
0
977
4
-1
1
663
13...

result:

ok 2000 numbers

Test #22:

score: 10
Accepted
time: 62ms
memory: 105088kb

input:

2000 2000 2000
1853 1944
457 1237
1133 1761
1205 1106
605 1166
1175 97
722 909
681 359
852 1716
1935 268
1 1588
1900 1082
1868 588
1179 1345
1493 1106
482 52
276 156
1880 1905
497 858
290 640
1508 531
1753 1886
923 1865
661 569
1689 1787
962 992
858 1424
807 524
1212 1556
1608 1783
1251 1686
1337 30...

output:

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

result:

ok 2000 numbers

Test #23:

score: 10
Accepted
time: 32ms
memory: 105224kb

input:

2000 2000 2000
1108 1148
1264 1635
127 216
1391 874
548 1746
855 1360
1887 1620
1 1707
1584 804
70 149
796 1344
366 764
677 1199
1247 1549
1265 1122
1052 777
1598 1340
691 1897
669 543
103 1182
1644 1774
1609 1588
1758 1736
745 1752
953 1067
1526 1391
397 908
1616 1360
1056 1657
1399 123
1783 1088
1...

output:

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

result:

ok 2000 numbers

Test #24:

score: 10
Accepted
time: 47ms
memory: 100860kb

input:

2000 2000 2000
255 874
1314 518
1597 995
1523 580
1776 886
184 1078
1756 1297
1090 1345
797 974
816 1707
190 915
89 933
1109 615
812 148
526 1133
1212 1444
1354 1171
309 583
1693 648
1934 1728
1408 945
1099 1120
306 1526
1019 854
39 848
1517 467
472 1719
1387 1446
1411 930
1527 1512
1902 108
2000 14...

output:

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

result:

ok 2000 numbers

Test #25:

score: 10
Accepted
time: 39ms
memory: 102964kb

input:

2000 2000 2000
1489 758
1279 791
1681 1107
363 1170
1181 958
1186 897
577 1482
1540 556
810 1555
1897 580
1121 127
104 78
811 1916
1559 817
1062 112
889 769
298 343
716 660
1101 1115
801 712
1037 1332
622 1276
1322 731
430 1892
1048 1880
498 1778
1180 226
478 435
770 1750
1503 1989
854 1032
321 882
...

output:

0
0
0
0
8
0
0
21
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
6
31
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
-1
0
0
9
0
0
0
0
0
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
7
0
0
0
0
0
6
0
0
0
0
0
0
0
0
...

result:

ok 2000 numbers

Test #26:

score: 10
Accepted
time: 53ms
memory: 104240kb

input:

2000 2000 2000
1561 1398
424 826
141 904
547 1655
55 634
310 555
1370 22
530 1867
1694 1314
818 698
1653 1855
1925 509
1336 278
1835 1862
1938 270
611 1312
1503 812
289 1952
473 657
831 1086
781 1062
609 1692
1693 336
197 324
1306 749
170 1584
1550 958
4 592
849 596
609 206
1470 415
1251 1619
1925 4...

output:

1
0
12
2
13
-1
-1
-1
4
9
3
4
0
11
-1
7
16
11
9
-1
25
-1
1
2
2
5
7
3
12
15
-1
2
7
-1
0
1
-1
-1
-1
-1
1
17
25
5
-1
-1
6
9
6
-1
-1
-1
17
-1
9
14
2
8
8
9
15
-1
-1
5
8
-1
-1
2
0
2
2
11
3
-1
-1
6
13
-1
4
-1
1
-1
-1
2
-1
-1
23
0
-1
1
6
10
7
-1
15
0
16
-1
1
1
6
-1
6
4
15
25
7
30
0
-1
1
17
22
-1
-1
5
-1
2
8
...

result:

ok 2000 numbers

Test #27:

score: 10
Accepted
time: 50ms
memory: 96840kb

input:

2000 2000 2000
1302 656
774 642
859 134
379 98
1620 537
1446 638
522 1333
1993 1818
1583 1629
42 1614
201 84
1211 1620
230 1431
1319 1917
1647 856
1967 1028
1872 1712
1116 1320
1322 948
1669 1943
689 871
272 656
972 113
1475 982
1579 530
1763 1418
1797 751
1864 1143
1951 782
1562 1804
510 1684
1759 ...

output:

13
13
10
-1
3
7
17
-1
23
5
3
3
0
12
8
-1
11
5
3
-1
6
7
8
2
7
8
4
1
8
5
7
18
-1
-1
11
4
4
6
12
13
-1
7
7
25
-1
11
6
11
1
4
-1
1
1
7
0
-1
-1
0
1
-1
-1
-1
14
16
4
-1
9
-1
14
3
6
16
7
21
2
-1
4
1
-1
-1
3
2
12
0
3
1
-1
8
2
-1
7
12
-1
9
13
3
8
18
4
5
-1
1
13
14
-1
14
4
0
18
10
0
9
3
11
10
12
4
3
10
6
6
24...

result:

ok 2000 numbers

Test #28:

score: 10
Accepted
time: 57ms
memory: 90808kb

input:

2000 2000 2000
221 1490
1700 403
501 1001
927 1491
165 960
1583 1136
284 446
1245 331
106 1922
995 363
1084 1011
1271 86
658 1259
681 589
756 1218
910 1716
944 1387
723 757
912 1457
773 867
1050 1825
1942 1077
186 1672
681 1401
1324 1559
374 1957
58 230
881 878
133 325
1326 1096
1475 215
549 602
185...

output:

16
0
14
0
3
3
-1
-1
11
7
-1
8
4
1
5
8
33
3
5
-1
14
15
0
8
11
13
0
0
3
-1
9
-1
0
8
13
14
-1
4
13
4
18
5
6
-1
2
8
6
1
-1
-1
16
-1
-1
0
-1
7
2
-1
14
10
3
4
15
26
5
19
3
5
-1
-1
-1
3
1
-1
13
8
5
15
-1
23
19
1
-1
-1
11
21
4
-1
-1
18
14
18
3
13
5
12
0
4
10
2
12
4
-1
13
6
8
2
3
14
8
26
-1
11
11
7
3
7
2
9
-...

result:

ok 2000 numbers

Test #29:

score: 10
Accepted
time: 51ms
memory: 94884kb

input:

2000 2000 2000
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:

348
55
510
-1
248
1713
217
-1
652
-1
18
74
-1
49
137
1558
1485
901
-1
341
42
-1
-1
1081
-1
-1
-1
-1
698
87
414
128
-1
6
502
833
659
955
60
731
143
366
167
266
320
249
36
-1
203
287
345
2057
405
384
179
1138
-1
356
82
5
253
191
1254
270
401
912
452
381
665
-1
615
751
329
836
18
-1
-1
66
-1
-1
220
88
...

result:

ok 2000 numbers

Test #30:

score: 10
Accepted
time: 49ms
memory: 104712kb

input:

2000 2000 2000
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:

90
1053
59
1149
-1
-1
-1
86
406
288
8
116
174
3
-1
881
-1
167
968
-1
365
-1
-1
-1
-1
-1
96
213
-1
101
-1
0
1821
-1
-1
-1
753
-1
8
-1
2496
832
-1
-1
102
139
1567
3
563
274
-1
1039
96
-1
-1
616
518
662
-1
304
-1
-1
220
1066
162
391
592
77
493
197
642
124
-1
41
821
226
-1
52
-1
-1
63
154
1514
-1
866
-1...

result:

ok 2000 numbers

Test #31:

score: 10
Accepted
time: 44ms
memory: 104808kb

input:

2000 2000 2000
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:

166
312
25
35
1400
1340
-1
608
946
120
118
184
202
353
92
-1
-1
-1
627
224
213
1545
21
219
366
-1
-1
-1
474
54
95
752
4
294
108
-1
136
-1
1457
132
-1
84
-1
17
755
-1
382
5
224
-1
139
115
378
98
165
-1
133
468
144
10
896
7
29
58
-1
-1
-1
485
-1
593
-1
5
51
942
558
1218
413
1094
-1
599
1238
315
401
96...

result:

ok 2000 numbers

Subtask #2:

score: 0
Time Limit Exceeded

Test #32:

score: 28
Accepted
time: 3158ms
memory: 124388kb

input:

99819 89735 60985
59741 24953
61387 12293
53761 1828
60970 60534
40598 48807
21876 21232
29527 13335
84269 40756
89571 12996
25757 40587
52477 63347
41372 69243
16391 58678
40854 39513
84384 91744
62938 60371
81932 45504
34121 54746
51945 14294
883 85344
78845 51797
45025 76590
37694 65493
4118 2588...

output:

36
-1
12
59
9
5
652673843
3
422622756
-1
-1
-1
29
-1
-1
-1
13
427634455
18
265926271
263974211
877045993
8
288833077
997549690
644774220
16
995218986
31
30
924036742
19
19
2
-1
10
-1
4393606
22
2
932888431
991013529
14
14
-1
6
-1
19
1
20
8
502124020
726366843
1
24
119719836
-1
25
217737158
-1
941591...

result:

ok 60985 numbers

Test #33:

score: 28
Accepted
time: 3720ms
memory: 127820kb

input:

65792 82260 98345
2807 36704
10610 16927
54219 65426
24263 25305
13397 46673
60999 3285
35985 24016
10517 9010
4968 22658
30974 31951
38242 17952
61100 8530
15143 8846
61270 11644
8471 2574
41231 48185
62800 35928
39726 5051
8526 43440
35896 29662
41894 56913
52781 49717
26456 16360
32511 37106
2284...

output:

8
5
882373032
23
1
1
-1
-1
356931161
39
341872751
7
443103688
21
477952848
-1
4
-1
753271794
262323059
532395174
11
21
16
16
24
853345123
816626114
4
772964226
431526730
-1
5
21
627951453
204273333
-1
401693620
984451652
-1
-1
18
29
-1
555626761
-1
875205996
-1
117944225
125509799
15
-1
10
238336545...

result:

ok 98345 numbers

Test #34:

score: 0
Time Limit Exceeded

input:

81509 65745 92452
49354 34810
8622 33343
50412 37468
49936 15350
28400 76011
5783 77041
61734 75149
67014 22641
4383 53957
28387 47981
31116 29067
75760 43023
23755 42103
47843 18332
62808 52998
5475 54810
28429 30311
66710 41985
27014 941
22865 26848
23077 70957
63837 44035
76582 15522
34929 56916
...

output:


result:


Subtask #3:

score: 0
Time Limit Exceeded

Test #59:

score: 30
Accepted
time: 2598ms
memory: 128088kb

input:

95629 64841 64314
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:

-1
701714740
-1
610354140
816755067
2440
245932872
-1
29509
866966613
744072492
890
-1
969398264
588051152
381506396
2347
5427
4829
44377
195466300
60823
508
459304253
400544113
-1
787773518
3856
9692
6576
322820913
900985028
1473
14691
26175
-1
27082
-1
9735
3846
537036842
-1
261459575
86658
635912...

result:

ok 64314 numbers

Test #60:

score: 30
Accepted
time: 2582ms
memory: 130008kb

input:

92502 51399 68929
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:

36266
-1
-1
112572200
27068354
-1
10394
329233107
444229297
223185833
363055390
1754
14433
-1
4346
-1
33082
457460095
-1
5482
749013593
717085104
5006
-1
926464006
1983
589805099
7590
264497528
8979
903766762
24704
903
923960764
4211
53272133
17012
435443676
-1
984123705
-1
1980
-1
2907
20373
813690...

result:

ok 68929 numbers

Test #61:

score: 30
Accepted
time: 2973ms
memory: 130356kb

input:

53810 92751 89379
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:

462043454
6397
31647
98446547
81496
14
34784
1587
532169187
35742
753712897
400460299
299860851
-1
26049
984595650
8185
13794
721579357
166901630
16093
-1
48327
52280
-1
36956
49549
33065
703982006
15511
171757272
130683368
-1
16949
-1
96442497
948433381
-1
-1
-1
3
55603
-1
120939988
12974
952750599...

result:

ok 89379 numbers

Test #62:

score: 0
Time Limit Exceeded

input:

100000 100000 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:

22357
29573
45104
2184
-1
109258
31337
-1
26387
41578
8392
36172
1160
9470
-1
6923
-1
-1
302
26401
-1
52971
25666
1970
104774
-1
33764
-1
-1
43624
5470
26387
38352
-1
8495
8983
7396
8448
4711
72385
-1
4832
-1
5388
4583
1151
38790
30979
-1
17732
28535
45088
-1
-1
97310
15663
92961
12755
949
-1
22729
...

result:


Subtask #4:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%