QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#318857#7607. The Doubling Game 2arnold518AC ✓1326ms199228kbC++173.4kb2024-02-01 01:53:112024-02-01 01:53:12

Judging History

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

  • [2024-02-01 01:53:12]
  • 评测
  • 测评结果:AC
  • 用时:1326ms
  • 内存:199228kb
  • [2024-02-01 01:53:11]
  • 提交

answer

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 3e5;

const int MOD = 1e9+7;

struct mint
{
    int x;
    mint() : x(0) {}
    mint(int x) : x(x) {}
    mint operator + (int ot) const { return x+ot>=MOD ? x+ot-MOD : x+ot; }
    mint operator - (int ot) const { return x<ot ? x+MOD-ot : x-ot; }
    mint operator - () const { return x ? MOD-x : 0; }
    mint operator * (int ot) const { return 1ll*x*ot%MOD; }
    mint operator += (int ot) { return *this = *this + ot; }
    mint operator -= (int ot) { return *this = *this - ot; }
    mint operator *= (int ot) { return *this = *this * ot; }
    operator int() const { return x; }
};

int N;
vector<int> adj[MAXN+10];
int sz[MAXN+10];

mint dp1[MAXN+10];
mint dp2[MAXN+10][21];
mint dp3[MAXN+10][21];

int clz(int x)
{
    if(!x) return 32;
    return __builtin_clz(x);
}

void dfs(int now, int bef)
{
    sz[now]=1;
    vector<int> chd;
    for(int nxt : adj[now])
    {
        if(nxt==bef) continue;
        dfs(nxt, now);
        sz[now]+=sz[nxt];
        chd.push_back(nxt);
    }

    sort(chd.begin(), chd.end(), [&](const int &p, const int &q) { return sz[p]<sz[q]; });

    vector<mint> V[2];
    V[0].push_back(1);
    V[1].push_back(0);
    for(int i=0; i<chd.size(); i++)
    {
        int nxt=chd[i];
        int k=__lg(sz[nxt])+2;
        if(i+1==chd.size()) k=min(k, __lg((int)V[0].size())+2);
        k=min(k, 20);
        vector<mint> V2[2];
        V2[0]=V2[1]=vector<mint>(1<<k);
        for(int j=0; j<(1<<k); j++)
        {
            if(j<V[0].size()) V2[0][j]+=V[0][j]*dp1[nxt];
            for(int p=0; p<k; p++) if((j&(1<<p)) && (j^(1<<p))<V[0].size()) V2[0][j]+=V[0][j^(1<<p)]*dp2[nxt][p];
        }
        for(int j=0; j<(1<<k); j++)
        {
            if(j<V[0].size()) V2[1][j]+=V[1][j]*dp1[nxt];
            for(int p=0; p<k; p++) if((j&(1<<p)) && (j^(1<<p))<V[1].size() && clz(j)==clz(j^(1<<p))) V2[1][j]+=V[1][j^(1<<p)]*dp2[nxt][p];
            for(int p=0; p<k; p++)
            {
                if(j&(1<<p) && (j^(1<<p))<V[0].size() && clz(j)!=clz(j^(1<<p))) V2[1][j]+=V[0][j^(1<<p)]*dp3[nxt][p];
            }
        }

        V[0]=V2[0];
        V[1]=V2[1];
    }

    int k=min(__lg((int)sz[now])+1, 20);
    for(int p=0; p<=k+1 && (1<<p)-1<V[0].size(); p++)
    {
        dp1[now]+=V[0][(1<<p)-1];
        dp1[now]+=V[1][(1<<p)-1];
        
        dp2[now][p]+=V[0][(1<<p)-1];
        dp3[now][p]+=V[0][(1<<p)-1];
    }
    for(int p=0; p<=k; p++)
    {
        for(int q=p+2; q<=k+1; q++) if((((1<<q)-1)^(1<<p))<V[1].size()) dp3[now][p]+=V[1][((1<<q)-1)^(1<<p)]+V[0][((1<<q)-1)^(1<<p)];
    }

    // printf("NOW %d\n", now);
    // for(int i=0; i<V[0].size(); i++) printf("%d ", (int)V[0][i]);
    // printf(" : V0\n");
    // for(int i=0; i<V[1].size(); i++) printf("%d ", (int)V[1][i]);
    // printf(" : V1\n");
    // printf("%d : DP1\n", (int)dp1[now]);
    // for(int i=0; i<=k; i++) printf("%d ", (int)dp2[now][i]);
    // printf(" : DP2\n");
    // for(int i=0; i<=k; i++) printf("%d ", (int)dp3[now][i]);
    // printf(" : DP3\n\n");
}

int main()
{
    scanf("%d", &N);
    for(int i=1; i<N; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, 1);
    printf("%d\n", (int)dp1[1]);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 7ms
memory: 62388kb

input:

5
1 2
1 3
1 4
4 5

output:

21

result:

ok single line: '21'

Test #2:

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

input:

1

output:

1

result:

ok single line: '1'

Test #3:

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

input:

128
11 32
116 81
65 4
117 47
5 81
104 30
61 8
82 59
95 20
92 29
29 127
97 39
123 33
59 128
115 33
83 67
74 16
77 33
64 73
124 123
8 127
61 51
101 122
35 90
119 116
112 27
81 93
109 123
54 1
119 100
116 16
65 47
67 27
22 105
76 87
36 39
27 96
72 31
91 123
21 105
118 12
110 48
121 72
14 115
24 16
106 ...

output:

508800953

result:

ok single line: '508800953'

Test #4:

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

input:

256
53 177
57 242
74 90
107 104
209 169
132 70
152 142
71 168
143 99
91 130
202 140
49 165
209 193
209 137
159 188
247 48
49 21
20 208
155 185
120 231
83 87
37 84
143 18
106 8
114 79
191 158
208 256
133 252
215 92
199 108
166 168
39 217
85 69
204 139
100 75
111 6
230 198
79 130
26 155
155 38
55 81
1...

output:

999869740

result:

ok single line: '999869740'

Test #5:

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

input:

512
507 193
168 152
48 369
273 170
101 349
160 261
438 197
446 224
125 264
210 131
272 218
361 85
226 119
57 33
229 89
37 317
130 417
30 470
435 300
499 417
132 260
196 430
119 117
157 260
207 151
368 277
188 371
214 330
484 228
96 94
97 442
251 461
443 248
163 207
306 147
346 90
457 112
436 222
364...

output:

37387055

result:

ok single line: '37387055'

Test #6:

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

input:

1024
340 598
1 851
245 819
414 736
996 316
300 284
924 407
532 557
362 178
1006 469
397 373
742 77
112 37
406 892
703 666
496 825
1002 100
875 856
263 975
227 6
288 389
661 437
160 626
833 770
912 837
405 628
466 686
45 629
59 13
163 991
1017 422
208 247
344 376
709 956
570 272
996 954
518 454
267 3...

output:

689180079

result:

ok single line: '689180079'

Test #7:

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

input:

2048
2046 1942
589 1449
1593 1983
936 414
387 184
1962 1237
1986 635
573 1619
1598 1109
458 836
1123 1563
1502 519
1467 347
1815 864
980 405
709 433
1682 211
1967 1915
1089 1902
564 211
128 1004
1568 315
293 494
1552 1772
1641 1157
431 1899
1334 1623
161 1870
885 1330
1863 502
1761 1643
692 1759
118...

output:

275839338

result:

ok single line: '275839338'

Test #8:

score: 0
Accepted
time: 11ms
memory: 62992kb

input:

4096
2546 3568
3084 3426
1262 2128
1773 1455
425 3750
3444 3265
3099 464
3479 3651
639 1727
2486 2768
1165 1905
1847 2626
1335 3938
2550 1594
1520 1758
3771 2227
3486 60
381 383
1268 2829
1884 3468
3195 2892
983 31
584 2599
2811 1876
1875 3310
3184 2941
2893 202
1305 1926
1019 1639
3529 1998
2129 12...

output:

99235843

result:

ok single line: '99235843'

Test #9:

score: 0
Accepted
time: 19ms
memory: 62824kb

input:

8192
5663 2164
3712 1600
336 2388
1971 4169
1579 7319
496 8080
5305 982
5508 5777
5324 6680
4636 6745
7295 6086
6948 388
5239 811
1875 7271
5755 2864
2933 795
6448 6716
3016 302
2474 2937
6355 5936
4973 4064
2920 2318
6254 4090
665 2500
961 8180
5416 6371
4958 5430
7905 5013
4373 3068
6557 3867
3056...

output:

79832799

result:

ok single line: '79832799'

Test #10:

score: 0
Accepted
time: 40ms
memory: 63064kb

input:

16384
4535 8823
5344 1240
5793 15361
8423 14130
14595 11420
12195 1332
9712 4829
9533 14608
1328 14962
13846 1173
12823 5702
3518 9298
3235 13113
14312 3915
3439 9003
4667 5401
3819 2395
13827 981
3557 11804
7369 11344
15524 1435
4706 15539
12838 2109
4986 5367
2766 4313
6802 12338
12059 3998
6327 5...

output:

732760598

result:

ok single line: '732760598'

Test #11:

score: 0
Accepted
time: 87ms
memory: 63912kb

input:

32768
18706 23242
17650 5918
17278 24553
13070 18006
22702 10359
7113 13886
25578 16957
28955 27352
7353 6627
24042 21572
4744 30083
29267 16077
19328 1154
32271 23711
22390 3651
19272 7150
19081 13949
22123 4853
17958 18148
27675 28239
29486 26616
14292 23782
12790 18303
25184 9656
2671 13229
21875...

output:

383548244

result:

ok single line: '383548244'

Test #12:

score: 0
Accepted
time: 193ms
memory: 65236kb

input:

65536
58488 63309
5892 23044
42057 26219
45788 13164
16585 3001
4262 20408
60289 43446
44684 60172
60763 38228
56279 19103
45476 53988
42692 16285
17169 4001
23321 935
41892 8086
46236 15394
679 21542
26763 36111
47813 62044
22621 35997
6381 14778
17034 21699
54381 53287
35694 34830
14902 30504
5158...

output:

440039161

result:

ok single line: '440039161'

Test #13:

score: 0
Accepted
time: 6ms
memory: 62424kb

input:

2
2 1

output:

3

result:

ok single line: '3'

Test #14:

score: 0
Accepted
time: 440ms
memory: 68384kb

input:

131072
51230 116074
14356 18985
97302 87862
20350 65669
81694 54472
94257 44656
77121 118912
81235 115171
106881 104061
82683 25663
68305 12450
29336 62646
32572 74421
102407 112028
122054 79222
70569 123539
8651 78501
204 34510
69520 18129
55082 68106
51505 114323
100795 60383
61023 59864
57018 337...

output:

776456918

result:

ok single line: '776456918'

Test #15:

score: 0
Accepted
time: 1060ms
memory: 80916kb

input:

262144
131863 89153
74747 38646
187112 232634
203855 116743
1197 3109
104299 20430
195824 110378
144817 150658
187558 66008
261366 71448
227156 246386
4149 219771
47465 87425
185952 150310
20653 103389
4917 221350
124004 104544
162181 144076
79557 176106
88679 240655
234082 52601
205629 150797
20194...

output:

777533279

result:

ok single line: '777533279'

Test #16:

score: 0
Accepted
time: 354ms
memory: 199228kb

input:

300000
200042 33358
146127 282853
18162 208274
88763 197176
219535 47504
18973 156413
135038 231317
236314 79984
54777 75970
263068 185590
178314 16697
46633 171708
244101 108105
262612 237866
278911 257361
223742 114478
189208 195065
226678 182830
43889 137857
43488 17945
129846 57509
272492 132190...

output:

528233774

result:

ok single line: '528233774'

Test #17:

score: 0
Accepted
time: 392ms
memory: 152888kb

input:

300000
176764 78952
106987 49376
199197 145137
284233 133549
153566 146492
192389 171608
126109 165447
243592 22382
235466 121116
184443 97521
282334 9814
156 188663
107376 36037
157844 51710
62907 257468
246294 216846
219236 183284
216849 220858
269297 95886
219479 273154
165259 18296
162990 56046
...

output:

750813860

result:

ok single line: '750813860'

Test #18:

score: 0
Accepted
time: 394ms
memory: 122444kb

input:

300000
158309 149704
128435 163070
84245 49253
264263 44739
68743 180951
108361 147453
240926 297856
89945 260111
277457 169826
291582 125079
277648 144954
101400 245176
23891 241280
63493 241546
201991 83439
148391 183664
21371 262320
204841 29292
277535 194623
82560 91044
150547 79025
123803 68605...

output:

580868875

result:

ok single line: '580868875'

Test #19:

score: 0
Accepted
time: 553ms
memory: 97188kb

input:

300000
199668 175926
193518 215061
170371 258103
194712 162222
88766 94800
184812 295037
168857 181854
69199 242470
1818 80752
69395 194806
57376 42758
141192 88538
33986 256933
69427 76218
185239 91491
285920 41676
51905 1936
239856 132282
227388 41622
272706 124375
32038 284692
135219 69014
34936 ...

output:

381083020

result:

ok single line: '381083020'

Test #20:

score: 0
Accepted
time: 1300ms
memory: 82384kb

input:

300000
67567 276022
264241 227037
38178 145820
228201 233793
98899 138819
98797 261326
115390 242282
211578 259087
45319 276116
122811 28871
50088 69991
37258 200859
136470 175283
260338 91948
67384 212375
40231 149234
232658 26091
154421 76753
112123 10499
206637 278186
61238 227139
159931 11377
15...

output:

526946130

result:

ok single line: '526946130'

Test #21:

score: 0
Accepted
time: 435ms
memory: 122984kb

input:

300000
298283 154255
105673 91459
90712 551
123440 38867
273284 278037
289955 200645
67178 171102
262920 263155
13243 20544
3484 121690
144944 96882
36832 165786
136889 268839
113999 205529
215711 155237
265165 11117
297845 242471
256546 75078
105444 191232
129806 32926
47865 212371
242475 12162
140...

output:

454830106

result:

ok single line: '454830106'

Test #22:

score: 0
Accepted
time: 427ms
memory: 91100kb

input:

300000
255425 265169
133485 277287
76214 259004
64909 31394
38195 194625
113083 60995
114801 95891
252179 236591
174951 140502
120096 268047
112333 255250
40951 239609
183553 195051
267304 249424
251541 179061
141939 127130
185987 132693
168331 40484
168910 263246
133239 174144
98110 219653
71323 58...

output:

7085656

result:

ok single line: '7085656'

Test #23:

score: 0
Accepted
time: 416ms
memory: 83996kb

input:

300000
231673 112053
254937 146031
82044 136077
65848 14401
248803 96417
78006 18885
141370 451
117569 281482
106784 22636
276187 72289
42145 271720
31090 107912
4141 157651
83282 122287
145094 83114
43582 186660
256861 15404
236538 287383
243614 211230
151496 85034
38002 36984
2314 240792
193219 10...

output:

877977717

result:

ok single line: '877977717'

Test #24:

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

input:

3
1 3
1 2

output:

5

result:

ok single line: '5'

Test #25:

score: 0
Accepted
time: 735ms
memory: 81356kb

input:

299996
296442 185267
50530 274959
28270 115154
148934 249346
160551 84859
233979 154571
22843 135379
230333 236666
298334 183640
92347 194511
173381 25598
266261 136089
287505 185015
146778 296343
66934 86330
153692 167515
208193 268597
182346 21400
267740 194767
257287 155399
234463 206144
132725 4...

output:

958748728

result:

ok single line: '958748728'

Test #26:

score: 0
Accepted
time: 962ms
memory: 80104kb

input:

299997
69620 286151
83759 122458
150200 40713
27544 54012
96245 59812
180550 99731
217930 120974
163696 30804
275834 168480
207497 230467
132307 225351
20315 288360
29579 521
199710 78596
245633 262159
274256 35936
86684 131322
261721 211569
195864 72963
280835 83850
183385 296530
294024 176405
4753...

output:

384944882

result:

ok single line: '384944882'

Test #27:

score: 0
Accepted
time: 1081ms
memory: 80864kb

input:

299996
148922 127667
277673 197441
29052 20205
142405 266143
108859 287840
211351 181923
203021 23645
77544 40249
166846 291754
250262 146814
142031 39641
38402 279245
170977 184733
154573 124357
14071 146937
212153 285641
1200 73289
56741 83581
142675 90910
34133 76301
63971 24486
180535 141586
268...

output:

971339277

result:

ok single line: '971339277'

Test #28:

score: 0
Accepted
time: 1220ms
memory: 80380kb

input:

300000
25217 119027
159658 129611
152346 126715
76257 239862
233425 241260
187090 97105
81341 83145
30473 53950
155583 160833
167171 33346
34676 267326
225722 210758
237341 282776
212099 153785
193336 57133
276500 78517
85066 68912
97119 251080
56196 52211
226615 249598
251391 205606
246132 131565
3...

output:

871187616

result:

ok single line: '871187616'

Test #29:

score: 0
Accepted
time: 1326ms
memory: 82328kb

input:

300000
102824 264542
97459 294443
207887 24517
86542 159734
258999 26536
50082 269866
238475 32007
93949 298385
228703 85982
137498 128652
255827 78235
283491 173194
73700 144605
220086 281986
132744 8302
144861 107759
79676 170516
170650 203290
127771 293088
132201 132047
79581 216013
181179 266867...

output:

99010450

result:

ok single line: '99010450'

Test #30:

score: 0
Accepted
time: 1156ms
memory: 82348kb

input:

299996
242479 24995
122936 54434
10553 59084
232524 82036
297620 237283
237495 230131
251637 161635
241458 127410
230096 186466
125271 158610
63285 152286
118009 247683
83334 100530
74546 44699
62150 141585
239718 190019
107197 156126
61127 250943
226268 25100
85759 293768
217704 271966
38189 44651
...

output:

7871987

result:

ok single line: '7871987'

Test #31:

score: 0
Accepted
time: 907ms
memory: 80544kb

input:

300000
141120 87300
194322 170645
229819 142275
41425 298988
299047 109602
88400 186578
26657 236944
254960 49349
81333 19904
154061 156416
159858 5611
23618 127658
267627 222399
129713 170839
32424 220570
79761 69615
23754 150751
159615 217322
217327 16059
128031 112745
216426 255856
7377 182023
17...

output:

800979809

result:

ok single line: '800979809'

Test #32:

score: 0
Accepted
time: 734ms
memory: 76960kb

input:

300000
187459 276511
13204 112858
283815 276191
216613 271575
141969 92717
192257 110307
201403 277104
230595 155995
97518 49107
196198 299078
44975 1963
263278 272852
13453 8890
287918 22659
178192 78528
164812 271085
83986 14827
32133 247475
125396 3364
154483 90786
176446 208266
109982 172113
241...

output:

808644428

result:

ok single line: '808644428'

Test #33:

score: 0
Accepted
time: 632ms
memory: 74288kb

input:

299996
188752 101719
279316 246986
234432 243419
272970 705
38885 125692
240413 78732
273782 184744
211520 114706
90561 155300
15819 98642
155001 197334
176234 106386
230375 27141
159458 105976
43931 251797
277213 32451
178296 156807
3676 281605
157162 90450
60940 129806
130286 169475
285884 289386
...

output:

379195932

result:

ok single line: '379195932'

Test #34:

score: 0
Accepted
time: 784ms
memory: 155012kb

input:

300000
237729 123037
157430 246971
184400 158079
30617 11884
31953 246475
131242 106766
264888 224761
125361 26673
60635 106163
160321 262774
230455 159426
140331 83773
155773 191180
158116 83790
67422 218479
261855 78986
252389 128069
15587 19850
206767 152122
45054 44339
253201 270428
42310 112952...

output:

519652329

result:

ok single line: '519652329'

Test #35:

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

input:

4
1 4
2 3
3 4

output:

13

result:

ok single line: '13'

Test #36:

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

input:

300000
11262 192408
116072 24230
187003 272190
273685 210077
170965 38577
194980 295045
33802 190819
64796 200244
15854 4901
202070 198383
290577 17054
107551 141242
136681 75729
227834 27837
83600 69127
15544 192976
155253 272248
30643 269233
239057 254976
220514 163342
127578 161160
237442 44536
2...

output:

412009401

result:

ok single line: '412009401'

Test #37:

score: 0
Accepted
time: 882ms
memory: 97556kb

input:

299996
109754 77210
195890 236220
252772 122307
44379 284046
257265 245023
201955 113521
274770 82921
236926 282039
30764 7873
248940 138345
94397 171146
218010 228599
89329 5521
98515 247653
142110 275931
89149 206620
219431 221691
220173 140322
267768 192657
17204 134951
157598 243149
65102 174137...

output:

896924076

result:

ok single line: '896924076'

Test #38:

score: 0
Accepted
time: 628ms
memory: 78124kb

input:

299999
126262 52144
78038 52144
52144 71458
218142 43724
185628 234525
37447 36821
119760 217021
148818 187846
52144 227498
169948 52144
65195 219140
120149 264074
183247 135413
77629 109688
88071 52144
268556 52144
94175 52144
52144 155393
52144 48570
264251 211414
4769 52144
155619 13823
119908 52...

output:

922233830

result:

ok single line: '922233830'

Test #39:

score: 0
Accepted
time: 628ms
memory: 77596kb

input:

299998
262666 99862
298623 173860
196093 269451
225987 81634
285462 21057
110397 225987
181437 192133
296580 57267
133501 225987
207916 238612
67612 120151
109912 296527
64179 128986
66658 298489
225987 216620
276303 45001
181991 97579
225987 238471
117421 224099
15289 15336
81243 265559
226978 2066...

output:

200386114

result:

ok single line: '200386114'

Test #40:

score: 0
Accepted
time: 648ms
memory: 77580kb

input:

299995
132206 93434
255129 115353
39828 218427
22687 44088
117801 149340
218427 90394
183229 97959
86806 279070
170098 66127
218427 221218
92676 181005
181897 279135
114328 218427
263436 176830
176211 271149
276872 102528
194684 56875
242524 133069
187611 215162
232921 230888
133023 251923
1790 1901...

output:

889862190

result:

ok single line: '889862190'

Test #41:

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

input:

300000
264502 109576
246683 283217
198235 266061
166029 151283
137833 286166
37911 92576
205379 89225
183855 18620
12533 154831
286063 144540
299682 70971
215538 249304
159433 109021
10463 190917
103609 264927
274588 285646
215812 123993
178656 102048
99140 62296
164284 99357
66862 51528
221979 1629...

output:

279626666

result:

ok single line: '279626666'

Test #42:

score: 0
Accepted
time: 1205ms
memory: 99028kb

input:

299999
226238 107371
100479 182855
89746 102038
77305 15153
116370 143305
270006 63842
159821 276574
238124 251810
279162 217311
207209 42708
75436 247369
56009 57842
238929 105848
174002 182011
261290 239168
24910 252145
130991 115971
288645 192615
7625 154785
289457 126560
280015 116689
124520 121...

output:

851898051

result:

ok single line: '851898051'

Test #43:

score: 0
Accepted
time: 1145ms
memory: 83372kb

input:

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

output:

526946130

result:

ok single line: '526946130'

Test #44:

score: 0
Accepted
time: 1027ms
memory: 81912kb

input:

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

output:

501480625

result:

ok single line: '501480625'

Test #45:

score: 0
Accepted
time: 943ms
memory: 75880kb

input:

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

output:

61974700

result:

ok single line: '61974700'

Test #46:

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

input:

5
4 5
1 5
2 1
3 5

output:

21

result:

ok single line: '21'

Test #47:

score: 0
Accepted
time: 484ms
memory: 128904kb

input:

300000
272185 153047
193599 264882
287843 281709
113493 19804
264882 53086
3652 264882
229876 104245
287206 212099
264882 128931
157173 7257
297251 20941
264882 204460
264882 28491
44038 264882
297429 7563
4528 216865
145150 239709
264882 39775
264882 70344
264882 295495
256951 158743
264882 261699
...

output:

879544809

result:

ok single line: '879544809'

Test #48:

score: 0
Accepted
time: 788ms
memory: 113768kb

input:

300000
70460 248868
138961 208857
88861 279526
79164 177583
73945 229366
272541 272719
250497 26681
35087 192609
47506 238830
255262 39051
178560 148848
294086 269625
288932 145208
242423 89585
156534 82595
86715 276319
244925 272719
187916 272719
22624 253511
295788 163684
34098 65950
272719 236865...

output:

994214551

result:

ok single line: '994214551'

Test #49:

score: 0
Accepted
time: 1185ms
memory: 90040kb

input:

300000
77529 174362
112539 291134
202881 194748
133215 176041
263181 7810
156520 187389
109147 244520
233168 21587
259954 256519
58134 53627
126127 158289
168342 221684
246397 187592
196365 236915
265741 21779
31679 243282
128278 197577
157402 242819
93392 137814
178594 30929
196865 168815
180098 14...

output:

270972769

result:

ok single line: '270972769'

Test #50:

score: 0
Accepted
time: 848ms
memory: 77272kb

input:

300000
72584 50313
263508 202488
248800 267144
95474 42397
10723 253483
64881 271509
141069 38461
159458 62206
186757 179932
178059 178228
116417 269104
1197 8288
223594 82144
143292 114090
125039 196129
219087 259238
247495 158600
242711 247144
205934 83253
187796 288415
208040 86557
183112 293452
...

output:

571335268

result:

ok single line: '571335268'

Test #51:

score: 0
Accepted
time: 681ms
memory: 74712kb

input:

300000
81526 66828
63521 109478
10997 232331
62336 50611
59672 203543
163817 279749
244410 290499
25528 78544
258809 176550
262716 6493
128538 285963
191047 17030
263804 166840
34401 214122
5536 134897
258108 283847
152932 25909
181738 207804
21334 218535
126708 260271
65201 215497
166569 284029
297...

output:

622559069

result:

ok single line: '622559069'

Test #52:

score: 0
Accepted
time: 856ms
memory: 80548kb

input:

300000
82528 7300
5274 236576
153035 12843
299503 109285
201445 110051
101162 237085
272223 291863
158954 155584
269547 101532
296678 2918
65437 223345
164042 296815
168146 296578
207653 270486
199358 19571
150343 185738
194416 44170
160735 89898
44607 121696
36893 161159
118146 71245
167147 128855
...

output:

523190683

result:

ok single line: '523190683'

Test #53:

score: 0
Accepted
time: 679ms
memory: 73564kb

input:

300000
131372 45159
5907 39195
84926 51180
148254 164086
84661 98672
222463 109379
84553 209233
175596 281509
216380 4739
54405 8367
30737 60341
147665 267703
220873 221184
47635 31447
18609 192390
41005 184862
282971 21811
44181 168976
117254 24530
234981 89571
261106 204123
244477 3562
164165 1435...

output:

660599294

result:

ok single line: '660599294'

Test #54:

score: 0
Accepted
time: 171ms
memory: 75404kb

input:

300000
191223 134229
191223 2328
191223 270337
191223 296983
191223 250705
14626 191223
191223 57735
3666 191223
145461 191223
46344 191223
191223 250824
281607 191223
191223 31633
191223 59963
174208 191223
93063 191223
89028 191223
191223 189162
75810 191223
191223 183328
191223 116089
123126 1912...

output:

599999

result:

ok single line: '599999'

Test #55:

score: 0
Accepted
time: 841ms
memory: 82684kb

input:

300000
67209 239151
106637 169351
130760 172832
81682 215392
172832 135138
90272 98050
271825 31439
92938 237910
148432 22815
145889 106705
203381 237791
122881 139133
14821 244175
271005 118226
81328 183055
28206 62377
205749 75013
90272 132737
165565 64302
157913 205535
33113 109145
53201 59682
12...

output:

239943550

result:

ok single line: '239943550'

Test #56:

score: 0
Accepted
time: 1183ms
memory: 82432kb

input:

300000
213072 88915
76523 60000
126038 268832
179980 220814
192182 138281
111672 90176
294323 232648
284877 252355
66382 102545
235649 234113
153166 16484
13312 239161
85530 9974
252906 15611
289982 196935
70950 139685
102293 4655
135820 297972
91558 27820
222495 262269
139017 160875
53420 202938
51...

output:

130790448

result:

ok single line: '130790448'

Test #57:

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

input:

8
2 1
7 2
6 5
7 5
2 8
1 3
4 2

output:

149

result:

ok single line: '149'

Test #58:

score: 0
Accepted
time: 821ms
memory: 106680kb

input:

300000
48013 147540
8629 294446
74977 145712
6156 213923
187550 271120
218691 20045
150106 243384
177561 238786
175802 16444
86387 130225
25462 112727
44951 102200
54183 248768
86816 188121
287585 7914
43928 240410
271528 36524
160529 38211
297793 45423
279279 146632
139878 223785
107160 60607
26063...

output:

147023629

result:

ok single line: '147023629'

Test #59:

score: 0
Accepted
time: 443ms
memory: 89292kb

input:

299991
260677 149279
181618 153448
6844 296912
123769 279340
90016 111907
47576 50457
288121 110740
66677 170750
143349 178334
146430 118397
126396 65242
57608 166835
224045 279622
178722 80440
7651 151006
179069 234097
64461 252424
74895 155194
35736 235797
207706 107869
48271 259152
93192 32762
16...

output:

883869919

result:

ok single line: '883869919'

Test #60:

score: 0
Accepted
time: 403ms
memory: 87908kb

input:

300000
485 116176
23279 170337
264584 138551
166897 241257
135491 114082
178559 298160
248257 113682
182062 217160
199178 66314
109111 58568
42191 234416
170052 217120
216898 86462
200547 151612
122787 173583
247987 214514
68958 264460
233339 179977
59178 215737
192831 226627
137379 293525
273266 10...

output:

54924001

result:

ok single line: '54924001'

Test #61:

score: 0
Accepted
time: 307ms
memory: 81800kb

input:

299952
89987 184268
171160 231190
126601 85792
290906 161037
228259 244548
21598 166431
144233 10163
243771 197809
201362 1847
14278 78879
177813 193199
200652 210913
60754 79
125683 264720
165927 189460
117493 12855
4299 284667
95367 263933
94710 290571
58624 41169
58454 11748
49344 102851
272631 4...

output:

746538008

result:

ok single line: '746538008'

Test #62:

score: 0
Accepted
time: 270ms
memory: 80340kb

input:

299969
133054 51199
114906 229220
201231 118910
102986 56291
211807 53002
40268 295615
285145 11221
267485 291516
85572 19116
1921 245985
236034 15261
215270 106786
38779 203979
12881 154153
33634 268173
92528 285809
107267 29507
9926 223541
232276 242461
208183 123977
220273 217665
22871 282794
267...

output:

763763216

result:

ok single line: '763763216'

Test #63:

score: 0
Accepted
time: 388ms
memory: 82684kb

input:

299966
111098 111743
68983 191497
279736 255477
11202 177507
68125 221297
243014 106572
137504 298914
209031 35218
200591 52110
219686 10944
176903 207653
81767 202329
124098 271649
232245 152386
59242 68865
59021 248183
138736 166612
164786 21981
149179 254931
236965 241864
274625 173017
298479 135...

output:

427383086

result:

ok single line: '427383086'

Test #64:

score: 0
Accepted
time: 425ms
memory: 80368kb

input:

299626
65494 173728
229224 84882
211764 64249
232260 139420
45740 200765
72860 72564
21017 11394
154711 107982
15952 92926
9834 267512
138261 61301
56939 94807
252092 29156
150614 254093
5511 148504
68492 65613
87619 213296
109997 16542
195465 272647
211332 56809
170411 83711
214109 286104
269308 14...

output:

292613384

result:

ok single line: '292613384'

Test #65:

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

input:

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

output:

10233

result:

ok single line: '10233'

Test #66:

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

input:

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

output:

27883650

result:

ok single line: '27883650'

Test #67:

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

input:

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

output:

966677517

result:

ok single line: '966677517'

Extra Test:

score: 0
Extra Test Passed