QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#628624#9230. Routing K-Codeslucky_cloudAC ✓119ms37552kbC++142.3kb2024-10-10 21:16:092024-10-10 21:16:10

Judging History

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

  • [2024-10-10 21:16:10]
  • 评测
  • 测评结果:AC
  • 用时:119ms
  • 内存:37552kb
  • [2024-10-10 21:16:09]
  • 提交

answer

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

const int N = 4e5 + 5;
int n, m, du[N], ans = 4e18, rt;
vector<int> g[N];
bool vis[N], flag;
struct dpnode {
    int k, b;
    int dep;
} dp[N];

void merge(dpnode &x, dpnode y) { x = {y.k * 2 + 1, y.b, y.dep + 1}; }
void merge(dpnode &x, dpnode y, dpnode z) {
    x.k = 1 + 2 * (y.k + z.k);
    x.b = (y.b + z.b) + min(y.k, z.k);
    x.dep = max(y.dep, z.dep) + 1;
}
void dfs(int x, int fa) {
    if (vis[x]) return (void)(flag = 1);
    vis[x] = 1;
    for (int y : g[x]) if (y ^ fa) dfs(y, x);
}
void dfs1(int x, int fa) {
    int cnt = 0, son[3];
    for (int y : g[x]) if (y ^ fa) dfs1(y, x), son[++cnt] = y;
    if (!cnt) dp[x] = {1, 0, 1};
    if (cnt == 1) merge(dp[x], dp[son[1]]);
    if (cnt == 2) merge(dp[x], dp[son[1]], dp[son[2]]);
}
void dfs2(int x, int fa, dpnode dpf) {
    int cnt = 0, son[3];
    for (int y : g[x]) if (y ^ fa) son[++cnt] = y;
    dpnode now;
    if (du[x] < 3) {
        if (cnt == 0) {
            if (dpf.dep <= 32)
            ans = min(ans, dpf.k + dpf.b);
        }
        if (cnt == 1) {
            merge(now, dpf, dp[son[1]]);
            if (now.dep <= 32)
            ans = min(ans, now.k + now.b);
        }
    }
    if (cnt == 2) {
        merge(now, dp[son[2]], dpf);
        dfs2(son[1], x, now);
        merge(now, dp[son[1]], dpf);
        dfs2(son[2], x, now);
    }
    merge(now, dpf);
    if (cnt == 1) dfs2(son[1], x, now);
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    if (n == 1) return cout << 0, 0;
    for (int i = 1; i <= m; ++i) {
        int x, y; cin >> x >> y;
        g[x].push_back(y), g[y].push_back(x);
        du[x]++, du[y]++;
    }
    dfs(1, 0);
    if (flag) return cout << "NIE\n", 0;
    for (int i = 1; i <= n; ++i) 
        if (du[i] > 3) return cout << "NIE\n", 0;
    for (int i = 1; i <= n; ++i) {
        if (du[i] < 3) {
            dfs1(i, 0);
            rt = i;
            break;
        }
    }
    dfs2(rt, 0, {0, 0, 0});
    if (g[rt].size() == 1 && dp[g[rt][0]].dep <= 32) ans = min(ans, dp[g[rt][0]].k + dp[g[rt][0]].b);
    if (g[rt].size() == 2 && dp[rt].dep <= 32) ans = min(ans, dp[rt].k + dp[rt].b);
    if (ans == 4e18) return cout << "NIE\n", 0;
    cout << ans << '\n';
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 4ms
memory: 15996kb

input:

4 3
1 2
1 3
1 4

output:

6

result:

ok single line: '6'

Test #2:

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

input:

4 6
1 2
2 3
3 4
4 1
1 3
2 4

output:

NIE

result:

ok single line: 'NIE'

Test #3:

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

input:

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

output:

NIE

result:

ok single line: 'NIE'

Test #4:

score: 0
Accepted
time: 80ms
memory: 29508kb

input:

200000 199999
172774 188052
195063 155577
38023 148303
30605 155047
170238 19344
46835 58255
154268 109062
197059 116041
136424 12058
42062 149807
109545 115380
132322 51106
16706 162612
62234 31319
195735 80435
173898 84051
19876 102910
186924 9136
123094 117097
145054 173049
137364 152731
82662 18...

output:

NIE

result:

ok single line: 'NIE'

Test #5:

score: 0
Accepted
time: 75ms
memory: 29140kb

input:

200000 199999
168192 30733
164413 46673
175210 2329
69389 67102
33991 152553
91061 55265
166724 117726
90148 157176
34831 12213
60756 105488
121891 155192
82202 155666
102083 156661
38968 75200
190004 107321
72436 92732
64314 65004
39210 91106
70455 173568
179742 29844
126232 19552
133509 110602
131...

output:

20980030044349

result:

ok single line: '20980030044349'

Test #6:

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

input:

4 3
1 2
1 3
1 4

output:

6

result:

ok single line: '6'

Test #7:

score: 0
Accepted
time: 77ms
memory: 29820kb

input:

199021 199020
189105 111001
147300 187047
67395 102319
25317 152109
56495 115535
11656 19974
119178 6528
84571 159100
198873 156684
21161 163040
91720 165273
168305 140152
104884 119802
131 177991
35930 74934
27528 278
177640 162738
118439 69472
20365 85043
184995 54207
64542 188847
97881 167717
188...

output:

NIE

result:

ok single line: 'NIE'

Test #8:

score: 0
Accepted
time: 83ms
memory: 30792kb

input:

200000 199999
145608 31176
94180 155303
112924 85699
196865 176102
34049 30841
84924 191665
164317 97582
10102 125492
114493 20622
127660 194591
183851 21461
167689 53839
59189 126425
135853 79950
173910 4196
8134 182272
42157 63799
5109 182005
197391 154014
93467 130380
1508 66644
129681 199910
677...

output:

25146839515965

result:

ok single line: '25146839515965'

Test #9:

score: 0
Accepted
time: 70ms
memory: 30576kb

input:

200000 199999
160386 189041
24452 73297
75992 87415
87012 116413
18645 2219
151007 100916
87623 77520
51217 45179
51633 67938
183428 99891
74684 129965
186795 70345
28743 22633
107782 28087
117185 78477
46846 176763
18968 80952
118201 35872
123906 140127
65784 66684
24802 134847
42591 150517
27123 1...

output:

9894117829832

result:

ok single line: '9894117829832'

Test #10:

score: 0
Accepted
time: 89ms
memory: 29256kb

input:

200000 199999
42958 26294
73743 94861
161036 525
22581 6649
152064 106483
126795 178801
147721 107972
43433 197974
75281 163319
170596 167054
180443 168322
1443 163261
197722 164837
144573 16585
6005 143774
195029 188032
112864 105465
108330 154314
138435 103667
66734 146178
15416 123293
22322 10216...

output:

28756428378750

result:

ok single line: '28756428378750'

Test #11:

score: 0
Accepted
time: 63ms
memory: 26392kb

input:

199000 199099
149311 147296
89797 115798
124184 88539
170531 79689
134688 98182
53272 56612
68205 106798
156914 76119
158177 131
29557 179794
35380 78679
72756 116830
122836 23339
33434 147647
193860 131424
52240 110141
166223 94852
47072 83029
156709 75295
184679 174874
52901 95437
137870 130531
58...

output:

NIE

result:

ok single line: 'NIE'

Test #12:

score: 0
Accepted
time: 119ms
memory: 28532kb

input:

199999 199998
27735 110383
157138 117109
21107 95911
27141 58936
1514 195135
106403 63473
66162 42639
21681 114598
53954 191710
110249 143780
40636 40124
11560 51678
2778 182082
60435 105451
198676 123935
67639 115704
176195 189982
52257 8366
99743 141742
147381 28925
190341 131308
159677 5040
6138 ...

output:

NIE

result:

ok single line: 'NIE'

Test #13:

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

input:

64 63
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
52 53...

output:

NIE

result:

ok single line: 'NIE'

Test #14:

score: 0
Accepted
time: 15ms
memory: 16536kb

input:

40030 40029
27049 14668
38975 18442
35811 5302
17535 12299
15998 29692
2477 9551
30589 13238
21558 20519
14120 37711
3010 28910
20472 29630
20470 30673
20684 12059
34197 17012
11419 29902
27976 6142
17829 29836
17033 1563
28681 11276
15975 4662
35715 1653
4390 29700
20484 19601
35245 22179
35694 105...

output:

7876944195050

result:

ok single line: '7876944195050'

Test #15:

score: 0
Accepted
time: 95ms
memory: 29728kb

input:

200000 199999
194326 144191
182448 172442
33303 58743
195157 142391
124650 181319
48631 75861
194887 75085
871 75209
128403 22324
1911 96598
172868 55033
158652 188139
96224 69860
69359 69490
184520 11792
191959 42157
131482 19144
107935 150093
67117 41377
9963 116441
65600 112397
64802 13426
37419 ...

output:

23606567643085

result:

ok single line: '23606567643085'

Test #16:

score: 0
Accepted
time: 85ms
memory: 30728kb

input:

200000 199999
52436 11641
79984 114804
111668 33543
137247 48090
9645 65795
184747 39611
11610 159313
22638 145697
63222 136367
32014 151563
93890 110893
116729 104704
156341 117458
98118 56463
18222 199014
16706 14372
187937 105132
117178 156199
38056 104887
72658 192287
171805 72070
114790 84610
1...

output:

23902024445030

result:

ok single line: '23902024445030'

Test #17:

score: 0
Accepted
time: 63ms
memory: 24220kb

input:

199000 199000
56063 29441
95944 92411
160503 142093
170757 96332
25224 46198
58983 137544
22176 91206
112508 87842
147759 138236
64654 75242
89467 126313
169923 41227
76585 85194
105242 18476
155335 62578
90527 108821
4035 170280
185455 189112
132037 25888
54529 101925
157500 26166
108961 86259
9757...

output:

NIE

result:

ok single line: 'NIE'

Test #18:

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

input:

1 0

output:

0

result:

ok single line: '0'

Test #19:

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

input:

63 62
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
52 53...

output:

10737418236

result:

ok single line: '10737418236'

Test #20:

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

input:

40031 40030
26578 5228
15299 28135
6016 20513
9336 32838
7661 35534
1535 15919
6750 24484
12971 28515
35233 3039
19322 9954
12834 31329
37396 28591
35252 16624
31292 11428
26214 31352
34810 2666
16739 33210
16918 11923
40008 18925
4887 17921
13040 22276
17563 13112
11518 18366
14528 4093
24225 19386...

output:

14145979718895

result:

ok single line: '14145979718895'

Test #21:

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

input:

1000 199999
604 484
954 820
91 541
904 310
668 766
595 5
51 946
216 943
896 447
732 702
416 367
409 634
301 847
981 844
730 350
964 313
296 117
941 104
274 497
670 597
324 805
265 248
71 747
681 795
458 762
241 703
543 158
270 706
192 677
212 10
121 263
603 858
455 610
18 104
806 366
846 914
334 408...

output:

NIE

result:

ok single line: 'NIE'

Test #22:

score: 0
Accepted
time: 74ms
memory: 29176kb

input:

200000 199999
168916 189843
109020 119772
81186 19849
7072 27937
174905 77802
164987 111000
198561 161204
62743 121413
149808 156301
75104 165109
112830 151209
72295 77101
76375 19204
136608 198378
76406 199590
57764 154129
48910 116785
111401 109977
87838 139157
77747 194517
112299 158877
185275 96...

output:

35299787196240

result:

ok single line: '35299787196240'

Test #23:

score: 0
Accepted
time: 77ms
memory: 30560kb

input:

200000 199999
144147 72071
114561 93962
18776 127417
130404 34047
106654 44269
877 20752
140480 199128
141143 78428
160246 101224
95841 5378
90561 149381
46943 61769
80221 35510
167564 130060
182389 63999
133132 155106
43012 117979
130191 22893
25824 68379
182453 163277
116025 191932
141767 110874
2...

output:

13471994708663

result:

ok single line: '13471994708663'

Test #24:

score: 0
Accepted
time: 88ms
memory: 30740kb

input:

199022 199021
136856 142915
168114 180648
114369 95091
125209 96808
93791 137894
89954 65498
26012 135123
122911 34709
176448 184389
128555 111094
191371 72347
80760 145410
51727 84726
103043 193579
141324 157740
171547 192675
187925 59783
25672 137859
18921 39802
116494 99049
160099 107838
174119 1...

output:

NIE

result:

ok single line: 'NIE'

Test #25:

score: 0
Accepted
time: 48ms
memory: 25408kb

input:

135166 135165
45419 54604
81453 105593
26402 28999
28608 89965
120776 48533
76603 106963
113574 58088
23777 56709
101693 65039
109717 38482
122783 96461
45844 84577
3082 128381
115407 39083
95790 43653
67587 105709
113512 39408
126194 36234
105195 76163
109746 69388
24031 57058
128212 37827
34749 40...

output:

58091192996351

result:

ok single line: '58091192996351'

Test #26:

score: 0
Accepted
time: 76ms
memory: 29328kb

input:

200000 199999
150717 119718
32056 73883
126212 34545
182533 28010
141402 149238
51959 139591
36371 50670
194752 107965
185788 1409
121675 108149
94700 143764
73222 150872
162334 198172
16821 83405
83067 4652
197790 133843
83898 98608
32319 22267
143182 134079
175348 199905
131416 48285
9468 106710
3...

output:

NIE

result:

ok single line: 'NIE'

Test #27:

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

input:

40032 40031
34094 27327
12483 36998
9590 15140
6825 17291
21512 14523
15997 35435
12683 11420
7412 34363
31608 21178
10745 31983
15950 34840
27919 37670
32231 11949
3665 23642
11903 28209
18678 39455
26052 11954
17609 17649
31093 29946
23007 18707
31229 280
20426 31569
13200 5992
16326 17750
25769 3...

output:

27538832545051

result:

ok single line: '27538832545051'

Test #28:

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

input:

200000 199999
125946 186376
46135 158303
30293 185162
33144 166227
108294 45473
11191 184006
153910 101067
159317 162799
57288 177375
2252 138193
132712 99328
149544 97675
170281 96724
75508 185069
28849 20704
123673 111393
22771 70952
55087 133008
187298 62738
16599 96660
154698 45861
166006 79880
...

output:

NIE

result:

ok single line: 'NIE'

Test #29:

score: 0
Accepted
time: 54ms
memory: 23220kb

input:

200000 199999
41295 166839
172502 151742
26771 101088
93341 20156
142549 198534
199851 45677
30164 126117
166839 101899
166839 96955
25771 196347
188077 166839
101750 59424
166839 147664
117410 129918
159681 166839
113507 131406
70324 151745
113689 166839
119444 118485
132056 166839
35514 159529
141...

output:

NIE

result:

ok single line: 'NIE'

Test #30:

score: 0
Accepted
time: 74ms
memory: 29756kb

input:

200000 199999
114980 121891
109260 118078
139913 32023
183184 97170
88566 59103
149879 49713
165756 49486
52156 58733
117202 14216
27626 28900
128687 158036
109354 125456
37622 165311
50517 190202
157928 139788
52886 26227
134844 62342
15315 133595
107917 8381
43925 188220
83018 151261
66406 64725
2...

output:

30751955923316

result:

ok single line: '30751955923316'

Test #31:

score: 0
Accepted
time: 73ms
memory: 29812kb

input:

197758 197757
104389 66015
48174 193201
177325 197091
31332 22071
46692 108776
31215 73910
6518 66392
168527 192351
70885 196659
184034 44755
132079 133733
68842 100006
111570 196109
135868 38249
55917 109692
53905 15420
184378 16304
31675 102688
156254 189613
10582 172614
13388 98708
188775 186387
...

output:

6290311228845

result:

ok single line: '6290311228845'

Test #32:

score: 0
Accepted
time: 79ms
memory: 31084kb

input:

200000 199999
37466 114613
14230 26940
176147 2551
36190 2738
140532 106567
74859 125761
144836 4420
54389 77331
73951 75842
26864 131572
90078 28292
154874 117936
62901 122268
160867 187750
106333 69783
110151 4888
85577 172312
70188 39343
131730 197564
124555 149752
86407 53688
14899 84750
114921 ...

output:

16174802609220

result:

ok single line: '16174802609220'

Test #33:

score: 0
Accepted
time: 60ms
memory: 24448kb

input:

200000 199999
28200 76591
136542 105856
46136 81505
35887 137406
120826 86780
140150 167095
168816 158960
35029 46037
136231 156888
13871 162096
113919 126163
27455 74017
110494 181343
21854 88215
42084 113678
168226 131202
71256 80675
89288 194628
49687 77121
17869 43743
157818 169246
172091 157272...

output:

NIE

result:

ok single line: 'NIE'

Test #34:

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

input:

200000 199999
198959 94474
158051 171547
183153 81239
161313 193974
53384 183762
21507 96477
39462 159455
65529 58620
96327 102171
24997 177842
169886 66541
54573 93966
63219 94567
147462 152325
191527 199773
56882 197948
73899 14750
952 49621
171931 84183
94966 142304
33674 55719
106310 137725
1174...

output:

33671076040923

result:

ok single line: '33671076040923'

Test #35:

score: 0
Accepted
time: 68ms
memory: 30192kb

input:

198910 198909
117033 13149
131323 143379
21780 4124
146795 21951
120626 22246
73380 115799
22030 99427
45238 163413
139757 64605
156247 96592
46297 46755
91861 191473
72706 140383
160948 152332
115760 133673
10496 44142
55039 33840
119586 190531
109010 26985
63600 33793
165480 147106
84760 49775
159...

output:

12574901998929

result:

ok single line: '12574901998929'

Test #36:

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

input:

200000 199999
170227 176171
143168 22356
100931 161222
166606 52199
195604 74657
101360 94781
70916 181981
43551 41809
136523 52315
3487 186164
167080 180671
179794 8972
140673 139719
87617 18540
189975 31648
5275 20085
47888 46038
7172 8641
13823 115237
33164 110984
183656 129771
88252 47256
186377...

output:

NIE

result:

ok single line: 'NIE'

Test #37:

score: 0
Accepted
time: 81ms
memory: 28876kb

input:

199005 199004
96254 58046
14686 53523
107149 174062
137278 194561
120685 95335
107523 11056
96814 8097
45199 129101
22628 11931
135946 187256
103014 29708
103001 86391
175816 153348
13018 23283
24118 133826
74462 136709
53217 57243
86573 145038
99518 141541
194359 190281
7880 9045
93979 155475
16292...

output:

312296042176

result:

ok single line: '312296042176'

Test #38:

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

input:

40033 40032
2154 1164
33120 28555
38292 26704
21902 16081
2756 39752
15584 29064
18139 28803
32937 11535
18452 23595
37404 3531
22804 19533
16334 19089
3131 30537
22156 27561
13053 22769
36707 28415
5259 6233
32716 3237
24398 2492
10791 7952
19294 18570
8185 11430
37520 29668
18323 27441
3646 33946
...

output:

NIE

result:

ok single line: 'NIE'

Test #39:

score: 0
Accepted
time: 88ms
memory: 29552kb

input:

200000 199999
198766 73576
184009 51185
180835 25714
57037 161245
84714 89859
173760 6981
126445 100224
96617 189967
196410 138698
168552 127903
89094 129833
81374 115771
141083 133921
150635 151875
136339 55804
119556 166718
45255 142518
183841 18160
48616 43896
69551 163607
141624 149193
119843 19...

output:

NIE

result:

ok single line: 'NIE'

Test #40:

score: 0
Accepted
time: 86ms
memory: 30672kb

input:

200000 199999
169834 61747
34777 185341
190231 99882
33510 49946
94234 33803
82733 187089
81837 147076
161232 155847
74544 139086
167927 97332
175330 63126
38380 2612
161062 55046
58959 141894
87901 173048
74465 76894
94443 164192
178791 124365
102420 96561
109829 70994
142711 182100
171526 137537
1...

output:

391751738316

result:

ok single line: '391751738316'

Test #41:

score: 0
Accepted
time: 89ms
memory: 30112kb

input:

200000 199999
52556 71547
188590 16644
109222 171797
4203 158443
171900 152158
61814 74699
17757 143903
4476 129216
107886 96684
4928 196483
91151 44834
66759 181905
135885 158420
106528 129866
85026 128594
97412 89566
177515 74406
133856 188520
179783 160127
182157 133993
30376 150482
50492 166467
...

output:

2187556739961

result:

ok single line: '2187556739961'

Test #42:

score: 0
Accepted
time: 80ms
memory: 30824kb

input:

200000 199999
178844 12552
45524 73417
107764 169560
105874 81661
89353 190047
45352 1703
86491 169699
188680 8474
69688 181487
83649 56925
174921 49326
46965 186672
6054 63923
108078 171604
77943 52207
195604 170095
75090 169854
59412 429
168067 13938
132044 175942
34972 162479
18789 121843
180434 ...

output:

851202917712

result:

ok single line: '851202917712'

Test #43:

score: 0
Accepted
time: 79ms
memory: 29160kb

input:

200000 199999
125610 37865
56969 1645
127245 130542
138721 49332
168270 19784
129697 125213
2363 45035
43667 130166
106279 122655
178565 21172
172887 155666
12381 144862
74621 10151
135319 92163
127137 127817
147255 67262
33831 97870
37560 58021
42922 163225
114846 62635
175379 17719
60763 75564
990...

output:

NIE

result:

ok single line: 'NIE'

Test #44:

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

input:

2 1
1 2

output:

1

result:

ok single line: '1'

Test #45:

score: 0
Accepted
time: 89ms
memory: 29304kb

input:

200000 199999
183836 41819
25152 154518
144355 194774
116614 144594
137558 16147
170205 169457
40400 70234
109662 10304
196476 142913
109203 171192
149284 31784
170400 66936
149681 112170
181864 130297
75531 46090
80711 137860
192126 81035
171788 192284
28040 98853
2984 70711
23270 121885
110709 174...

output:

12558760470859

result:

ok single line: '12558760470859'

Test #46:

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

input:

62 61
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
52 53...

output:

7516192764

result:

ok single line: '7516192764'

Test #47:

score: 0
Accepted
time: 89ms
memory: 30516kb

input:

199023 199022
128658 15558
19040 74088
45234 170923
143720 143631
19703 74127
108578 129009
52179 33871
165880 90640
61916 67803
97945 96955
92721 188348
182015 45601
121918 94221
188806 43327
136334 30461
129863 184350
136866 131231
106200 19868
144365 74592
139631 81541
85492 125292
19275 156259
1...

output:

NIE

result:

ok single line: 'NIE'

Test #48:

score: 0
Accepted
time: 92ms
memory: 28904kb

input:

200000 199999
144024 179186
140171 44219
176406 104519
186503 169951
162419 168698
119369 140300
11210 39865
23488 140273
59084 96070
159931 53191
17841 65165
165783 60676
104637 182173
4332 62227
24698 61202
77544 5561
65201 60381
96806 168834
23592 199240
101740 177869
143202 72915
183094 121376
8...

output:

21556510784001

result:

ok single line: '21556510784001'

Test #49:

score: 0
Accepted
time: 68ms
memory: 24408kb

input:

199000 199000
127186 198262
186789 28205
168052 70351
29220 50538
39702 153295
6439 186124
82357 129162
18130 128697
154810 176397
83254 153684
127058 77464
145328 123661
181471 307
5949 136832
155769 89759
178508 45759
176170 50862
128452 109267
85611 7911
135078 161587
28410 118441
158248 179681
1...

output:

NIE

result:

ok single line: 'NIE'

Test #50:

score: 0
Accepted
time: 90ms
memory: 29504kb

input:

200000 199999
12279 96510
56926 100418
70720 193500
83165 37488
38684 32323
140880 69595
117388 32436
89390 125091
196675 154743
126477 115935
52449 124347
103030 170679
8441 32643
100387 28160
89024 52242
185018 81986
133182 126287
120217 158421
49167 168801
93220 31901
113828 198127
131137 105029
...

output:

46214691502073

result:

ok single line: '46214691502073'

Test #51:

score: 0
Accepted
time: 70ms
memory: 29228kb

input:

196894 196893
57393 99865
100301 109766
171246 190487
105588 142612
81250 11309
22165 89920
21127 45301
132022 7034
28496 99710
101060 114625
55920 170908
61663 90390
23655 153763
179297 177824
186790 77418
125324 182545
162575 69402
7981 45108
86799 195115
69618 147063
107799 91764
5850 15395
10176...

output:

1577859878221

result:

ok single line: '1577859878221'

Test #52:

score: 0
Accepted
time: 85ms
memory: 30544kb

input:

199010 199009
617 79024
78775 141118
95068 58269
49745 55501
15163 100053
198630 89067
12708 13445
94924 57808
50643 188833
74302 67303
149656 193846
50542 75691
183334 163736
31295 57376
166508 124345
147765 138310
175357 112846
139051 94453
28120 103826
32284 54440
29821 66575
26216 122038
47379 1...

output:

318430896700

result:

ok single line: '318430896700'

Test #53:

score: 0
Accepted
time: 57ms
memory: 27204kb

input:

172030 172029
60081 13059
137029 54023
32749 130163
110144 94780
30188 27525
68158 83625
148193 104063
81880 27875
89942 87211
15715 8604
64600 69349
129319 48463
65036 68776
7259 125024
57646 46201
87413 49312
130691 109981
147765 73257
139800 150472
142882 21180
68196 132872
18233 25255
6340 6463
...

output:

163287266173801

result:

ok single line: '163287266173801'

Test #54:

score: 0
Accepted
time: 93ms
memory: 29300kb

input:

200000 199999
10622 26947
79406 46197
47924 197686
55632 32685
75041 181338
125000 61008
119816 11720
68682 184025
163585 84981
39215 71867
42291 132681
52895 26359
144920 30491
78041 157786
125143 4650
26170 120818
115267 105456
182271 87233
141307 61006
138242 132155
75693 147912
144529 132517
147...

output:

NIE

result:

ok single line: 'NIE'

Test #55:

score: 0
Accepted
time: 54ms
memory: 24908kb

input:

199000 199000
62357 113222
163354 96984
57284 3449
133673 143190
3613 124295
74072 76326
89182 72453
109245 61165
79951 32768
6057 135367
27053 173371
156143 55307
23300 155180
43998 184565
185327 180232
56640 100165
41320 51891
21977 187473
54602 56444
39085 22610
122865 74119
38037 195603
53011 19...

output:

NIE

result:

ok single line: 'NIE'

Test #56:

score: 0
Accepted
time: 71ms
memory: 30804kb

input:

200000 199999
27773 71543
170507 16784
114951 7208
24726 147563
1372 191134
184563 126885
189158 33344
170499 165251
145770 21127
147733 18715
108360 97007
138924 162494
100239 190818
187214 109178
47924 67467
56131 144590
7448 182306
29897 104183
5738 144317
78837 70990
181148 153992
118475 110902
...

output:

18511194572929

result:

ok single line: '18511194572929'

Test #57:

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

input:

4 6
1 2
2 3
3 4
4 1
1 3
2 4

output:

NIE

result:

ok single line: 'NIE'

Test #58:

score: 0
Accepted
time: 73ms
memory: 30688kb

input:

197182 197181
145546 11761
51082 56610
42033 58519
103847 105186
157812 180298
82515 115263
848 56509
16117 144504
120843 10781
98002 90543
67705 126394
112619 5493
30442 32668
70714 82115
9681 176107
188715 71565
23181 43857
22144 172808
26327 55190
61365 122593
78737 784
102347 29519
179904 23165
...

output:

3148632961305

result:

ok single line: '3148632961305'

Test #59:

score: 0
Accepted
time: 76ms
memory: 32120kb

input:

199020 199019
38982 104858
164971 188940
71674 153519
24273 48506
178136 119739
108298 192331
64795 118354
46943 192919
70848 35902
165622 153406
47021 92899
123284 79576
171601 155935
157861 92259
177021 142444
158717 145603
110095 126848
45207 138567
4775 80959
187730 135471
118582 52064
181143 18...

output:

NIE

result:

ok single line: 'NIE'

Test #60:

score: 0
Accepted
time: 82ms
memory: 30872kb

input:

200000 199999
198319 35313
129641 179918
18268 192630
155649 178456
225 171881
141057 181666
19484 1463
124276 159966
76009 61996
174178 196717
156888 153915
24768 15782
39827 42285
109295 35850
115398 150458
163129 129418
48548 167807
73354 75616
33650 193072
74375 133449
170454 88251
29003 146185
...

output:

NIE

result:

ok single line: 'NIE'

Test #61:

score: 0
Accepted
time: 86ms
memory: 30444kb

input:

200000 199999
158522 175369
24416 99762
126320 18025
96531 104112
166947 110300
140877 99465
6527 125378
88614 169142
105924 187367
21578 22987
192008 199798
36075 127280
185501 6511
148006 152838
74724 100260
171317 29984
59713 95979
74702 85596
149621 48475
149806 33200
166516 88975
86087 30865
54...

output:

9820482867364

result:

ok single line: '9820482867364'

Test #62:

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

input:

3 2
1 2
3 2

output:

3

result:

ok single line: '3'

Test #63:

score: 0
Accepted
time: 15ms
memory: 20616kb

input:

40034 40033
17523 36213
28522 1439
23357 36120
7451 15383
5347 9734
9189 10326
32499 10456
14035 18491
31276 34598
17234 6262
16461 6190
34343 24736
1216 24802
33717 2941
15877 20560
30951 8517
23216 27915
4161 25872
38694 37720
14419 6854
29433 21607
39604 18577
38024 17848
19539 36879
6730 2710
34...

output:

NIE

result:

ok single line: 'NIE'

Test #64:

score: 0
Accepted
time: 41ms
memory: 23364kb

input:

200000 199999
2663 139506
36676 139506
146803 139506
114391 166386
139506 37328
139506 87198
139506 121207
174352 139506
186367 139506
139506 72288
139506 3794
139506 85376
139506 198628
153923 139506
139506 178660
139506 59667
139506 136317
139506 76059
30748 139506
139506 92882
139506 75714
139506...

output:

NIE

result:

ok single line: 'NIE'

Test #65:

score: 0
Accepted
time: 100ms
memory: 37552kb

input:

200000 199999
36426 167454
120097 47575
149860 124362
189845 33325
143615 21801
61507 74444
137180 162209
94998 148647
195022 102289
31165 126574
97517 8738
95283 66836
196054 91093
94912 188640
176970 136556
193928 190953
56040 7553
12605 49984
172113 29158
174709 157946
192332 175803
177998 62083
...

output:

NIE

result:

ok single line: 'NIE'

Extra Test:

score: 0
Extra Test Passed