QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#80712#5522. F*** 3-Colorable GraphsLiberty12619AC ✓115ms16708kbC++201.4kb2023-02-24 22:18:022023-02-24 22:18:05

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-24 22:18:05]
  • 评测
  • 测评结果:AC
  • 用时:115ms
  • 内存:16708kb
  • [2023-02-24 22:18:02]
  • 提交

answer

#include<bits/stdc++.h>
#define x first
#define y second
#define int long long
using namespace std;
typedef pair<int,int>PII;
const int N = 2e4+10,INF= 1e15,mod=998244353;
int deg[N],cnt[N],id[N],rk[N];
vector<int>g[N],h[N];
void solve()
{
    int n,m;
    scanf("%lld%lld",&n,&m);
    vector<PII>edge;
    while(m--)
    {
        int a,b;
        scanf("%lld%lld",&a,&b);
        deg[a]++,deg[b]++;
        g[a].push_back(b),g[b].push_back(a);
        edge.push_back({a,b});
    }
    for(auto [a,b]: edge)
    {
        if(deg[a]>deg[b])swap(a,b);
        if(deg[a]==deg[b]&&a>b) swap(a,b);
        h[a].push_back(b);
    }
    for(int i=1;i<=2*n;i++)id[i]=i;
    sort(id+1,id+2*n+1,[&](int a,int b)
    {
        if(deg[a]!=deg[b])  return deg[a]<deg[b];
        return a<b;
    });
    for(int i=1;i<=2*n;i++)rk[id[i]]=i;
    for(int u = 1;u<=2*n;u++)
    {
        for(int v: g[u])
            for(int w : h[v])
                if(rk[w]>rk[u])
                {
                    if(cnt[w])
                    {
                        cout<<2<<endl;
                        return;
                    }
                    cnt[w]++;
                }
        for(int v:g[u]) for(int w : h[v])   cnt[w]=0;
    }
    cout<<3<<endl;
}
signed main()
{
    int T=1;
    //cin>>T;
    while(T--)
    {
        solve();
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 4356kb

input:

2 4
1 3
1 4
2 3
2 4

output:

2

result:

ok 1 number(s): "2"

Test #2:

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

input:

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

output:

3

result:

ok 1 number(s): "3"

Test #3:

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

input:

10000 20000
4570 11730
8803 16440
4257 15381
4455 17636
5256 13543
2172 18421
7735 17847
8537 16010
6175 12263
1079 13410
335 15901
3272 16233
7435 11454
4469 13374
1564 13416
1264 13446
7484 14510
8193 12267
628 15585
1388 11398
5444 19958
2059 18140
8947 13188
6214 17707
7940 12253
6726 11508
1839...

output:

3

result:

ok 1 number(s): "3"

Test #4:

score: 0
Accepted
time: 58ms
memory: 15616kb

input:

9999 199986
8408 17344
1353 16706
3364 17274
9410 10006
9387 19375
9169 18239
3930 12759
4728 11328
5192 17935
7616 19485
3138 12714
8595 18490
6020 15039
9319 17097
7842 16814
7644 18723
2190 10117
3971 13350
232 15408
6984 12842
6988 17196
9744 18905
6759 13371
4115 18937
1842 13513
6245 18736
207...

output:

2

result:

ok 1 number(s): "2"

Test #5:

score: 0
Accepted
time: 115ms
memory: 15468kb

input:

9999 199986
1284 14140
5071 12232
7015 15577
4211 14089
3764 14645
4634 19044
1944 18455
5249 19603
1607 10182
9986 19929
1132 18778
3848 10147
636 10961
1994 14118
5084 18986
4067 19483
2288 17337
3108 15530
2258 12709
9809 14997
4860 11548
1779 13012
5062 16123
7418 10293
7726 11733
1145 14062
369...

output:

3

result:

ok 1 number(s): "3"

Test #6:

score: 0
Accepted
time: 112ms
memory: 15736kb

input:

9999 199987
3436 14265
222 15269
5540 12401
4384 10718
6743 19890
8221 16226
9005 14140
9863 11639
2152 19586
2757 14815
481 13850
3599 12891
5952 10977
8143 17941
2026 15710
5910 16369
5513 10925
5772 12885
7065 11342
8361 17923
5299 13781
3196 10966
430 14596
550 13223
3256 17779
6078 13305
5648 1...

output:

3

result:

ok 1 number(s): "3"

Test #7:

score: 0
Accepted
time: 98ms
memory: 15552kb

input:

9999 199988
448 11962
23 11944
5051 16992
4694 15126
5619 18509
283 12368
9283 13749
8666 13468
9704 13819
1156 17681
5584 15047
4002 12020
4132 12330
6517 16453
6626 18447
6875 19095
1121 18883
27 13565
5156 16000
1038 19156
3115 10774
4188 16379
9700 11423
1821 15792
1829 19849
7895 14361
273 1171...

output:

3

result:

ok 1 number(s): "3"

Test #8:

score: 0
Accepted
time: 104ms
memory: 15428kb

input:

9999 199989
5094 18037
3735 11120
5076 12536
7197 15317
8382 16357
1120 10650
3029 15062
6786 14917
9050 18178
5310 16842
6801 19176
6684 13049
2642 10752
3258 18536
1547 14065
9941 16349
70 13658
8055 13817
4079 11228
5959 10779
180 12999
4796 14531
4736 14130
9587 15391
456 17458
2927 18426
8200 1...

output:

3

result:

ok 1 number(s): "3"

Test #9:

score: 0
Accepted
time: 99ms
memory: 15432kb

input:

9999 199990
7767 17384
2351 16592
1740 13435
6736 15343
2870 13927
2392 19280
6593 15197
1551 11497
4026 13218
9283 18493
6908 18472
3364 19987
3241 18025
9134 15503
3244 17055
3298 14535
3919 19196
8242 19849
7598 13197
3105 15864
147 11948
6903 12658
5141 17398
6969 12053
2662 17452
5764 14717
189...

output:

3

result:

ok 1 number(s): "3"

Test #10:

score: 0
Accepted
time: 84ms
memory: 15524kb

input:

9999 199991
3291 16273
226 18073
7487 15435
1491 16286
6130 13276
8585 16323
6842 11678
2111 17229
477 19001
3357 15937
8305 11249
1554 14466
4443 18841
3506 18862
5514 19459
3539 10480
3849 14524
1884 12492
6517 14698
8587 12383
4530 17389
4383 15441
9481 12847
4516 18050
2713 14163
2070 15055
9625...

output:

3

result:

ok 1 number(s): "3"

Test #11:

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

input:

9999 199993
2335 14493
9141 16214
1417 10716
5544 17576
4997 15035
5205 17840
3968 18790
668 17130
6035 10183
3278 18222
6202 15455
21 12990
9830 19493
2407 17362
4680 11842
6997 19101
4521 13784
1273 19776
827 15240
9596 15384
2875 11780
9312 16707
5649 12637
8663 12350
5566 17959
1619 12998
6490 1...

output:

2

result:

ok 1 number(s): "2"

Test #12:

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

input:

9999 199994
9458 14548
6018 19758
199 12677
4732 13451
4698 11128
8241 14617
6518 10875
8333 17651
2732 13675
2127 14984
1354 12015
2897 17058
6896 16037
546 12435
4340 18337
6250 15427
7454 13191
5207 10882
3690 19415
6265 14229
3573 17323
8269 14593
692 18301
7016 18103
1117 17097
7840 15596
2896 ...

output:

2

result:

ok 1 number(s): "2"

Test #13:

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

input:

9999 199995
2206 19276
8512 15696
6390 12136
4048 18969
2035 19175
7724 15620
7823 11377
2847 13114
6767 14065
5825 12916
5920 15627
9397 15431
8383 17174
2674 12767
3179 16759
1587 14186
4146 13179
4017 16558
1876 13548
9659 12440
9606 17367
7953 11024
6310 10073
8643 17223
9626 16601
441 17619
287...

output:

2

result:

ok 1 number(s): "2"

Test #14:

score: 0
Accepted
time: 67ms
memory: 15984kb

input:

9999 199996
363 19358
6951 18873
8851 19662
211 19818
6614 11711
9529 11595
7916 14951
7870 19632
1547 13402
4257 19275
4549 16778
6083 11064
5118 12638
779 15309
3010 14286
1917 15974
8333 12598
7558 17568
8737 14059
3060 12113
4318 10493
5121 14889
9485 13139
2279 12389
8040 11112
6623 16400
7760 ...

output:

2

result:

ok 1 number(s): "2"

Test #15:

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

input:

9999 199997
5538 15784
5775 19178
491 10172
7692 17593
9268 15603
9233 13637
2552 12658
1910 13501
8806 15179
1384 19199
1672 16094
9510 12151
7611 19538
729 19555
5125 18661
8910 18499
480 14200
4125 14316
8129 14814
7145 11770
924 12802
2278 11173
7323 17658
508 12939
9237 11184
4378 19856
3681 10...

output:

2

result:

ok 1 number(s): "2"

Test #16:

score: 0
Accepted
time: 104ms
memory: 15592kb

input:

9999 199997
3361 10129
4115 14259
1482 14425
2095 13283
1140 17857
8556 16601
4023 14864
5516 12856
6503 17450
2783 10817
4606 18604
7695 11174
7621 14012
2536 17077
9278 15989
9763 16626
3812 10052
5882 12772
6465 11058
6671 18514
9046 14814
7444 15541
7106 12077
8711 18841
878 10954
3093 16469
347...

output:

3

result:

ok 1 number(s): "3"

Test #17:

score: 0
Accepted
time: 111ms
memory: 15420kb

input:

9999 199998
9814 19377
9308 17674
8995 13703
432 17153
9285 18418
830 10685
4597 16742
5277 19909
9217 18218
9987 13899
1529 19955
7440 14275
7203 10641
5287 11358
2487 18971
1397 17738
7803 15822
9780 17091
6116 16949
3696 12404
3018 15579
6738 16989
1768 18020
2750 14215
7558 16485
2151 18902
9129...

output:

3

result:

ok 1 number(s): "3"

Test #18:

score: 0
Accepted
time: 62ms
memory: 15544kb

input:

9999 200000
1033 10643
4542 13953
4776 10664
846 17527
5840 14947
8166 11144
3957 18045
8736 12143
211 19534
4776 16656
9366 18999
7283 17898
8327 14611
2425 10379
7700 10503
4187 17095
4582 14627
7889 19818
3907 12486
1137 15302
2920 14818
9171 15782
5167 12958
9193 18056
314 19102
8264 13330
1943 ...

output:

2

result:

ok 1 number(s): "2"

Test #19:

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

input:

8150 16300
714 11376
415 9250
4911 9685
3451 11069
2331 8433
2557 13540
6968 9053
1738 8710
4664 12771
4134 14511
6520 13078
5331 9129
7564 11673
165 13262
4662 13935
3829 15954
4251 10582
5230 13764
3419 8820
1612 11731
4787 15243
374 12920
727 15373
951 14559
5137 14086
6349 13163
6603 9083
6892 1...

output:

2

result:

ok 1 number(s): "2"

Test #20:

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

input:

8313 16626
3971 10372
5856 11598
3636 15341
3819 15252
218 9509
3227 12825
7210 14905
7479 10723
3046 14780
4042 14078
4612 12075
5541 14615
6964 14947
7716 11357
3172 15952
5169 15794
697 10070
5251 14357
6125 12242
3504 8370
3807 11495
6742 11811
3521 13122
3201 14490
6397 12897
3928 14337
5965 16...

output:

2

result:

ok 1 number(s): "2"

Test #21:

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

input:

8476 16951
272 11630
72 12296
5589 10521
4235 13556
1225 10336
1119 10721
4548 10967
3798 13281
2638 16658
1305 9298
1627 11590
4504 14979
3895 8609
7656 12831
2123 9604
3840 9599
1805 9267
1157 10665
7374 13326
7871 10665
2558 15579
7835 12577
6042 14314
5604 16453
65 12172
105 12508
4525 16078
363...

output:

3

result:

ok 1 number(s): "3"

Test #22:

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

input:

8639 17278
3808 9002
7920 10789
2022 9697
4868 9149
476 16243
3035 15635
3267 13373
7695 12633
3295 14615
3211 9752
7564 15802
6022 9156
4591 13753
4072 11008
43 10536
6516 13136
1015 14141
2300 12314
4003 8733
5684 10961
104 16408
1591 9189
5936 16447
5065 16659
8051 12868
4533 9196
7171 15055
2947...

output:

2

result:

ok 1 number(s): "2"

Test #23:

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

input:

8802 17603
3149 13968
5101 9246
2111 17600
2284 16214
4100 9847
4778 9791
1148 12995
3967 8969
7841 13508
2550 10774
8693 11426
8184 12357
7311 11607
2644 8879
6133 17151
997 13228
730 17148
6144 9177
4551 17541
2508 10409
3744 10655
5254 12255
2876 17023
4622 8948
4107 8959
3018 11020
5363 10165
80...

output:

3

result:

ok 1 number(s): "3"

Test #24:

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

input:

8965 17929
7637 16678
6981 16236
851 9134
6034 13997
6808 17061
955 12544
8742 12320
4091 11549
2489 12442
7232 10825
7837 16645
5335 14031
963 14789
1788 9926
2570 11371
2667 10025
6530 12663
8718 12914
8005 14020
6081 17284
1201 9472
543 15546
3681 12809
331 14980
838 13661
1933 14967
8267 10945
1...

output:

3

result:

ok 1 number(s): "3"

Test #25:

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

input:

9128 18256
7782 13159
4087 10273
6257 12527
5070 16039
4690 16290
3469 12208
6174 11884
6012 10370
3425 15684
2385 16013
2673 17457
3690 18039
8993 15267
2378 17967
2738 17358
2646 11448
9021 12530
7506 14775
8655 15550
6074 17958
9087 14541
787 9776
8318 9500
3594 15645
782 17382
8909 15438
7461 14...

output:

2

result:

ok 1 number(s): "2"

Test #26:

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

input:

9291 18581
2001 13860
7812 12559
4773 12448
6668 11446
4040 16339
2356 17550
8323 15596
3403 16933
940 12927
1254 10168
4143 18463
2614 10103
2953 12664
5081 11692
8388 17073
8805 13758
7407 18029
7167 16152
7568 17141
6675 11890
694 15109
1656 17930
1728 11810
6933 12988
8893 14083
8955 14025
3968 ...

output:

3

result:

ok 1 number(s): "3"

Test #27:

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

input:

9454 18907
3536 15594
7328 16932
5114 10597
3849 17816
2504 12887
8574 16051
3988 18793
6792 14286
947 11681
3706 9611
5001 17521
2961 10013
7927 17140
3618 17017
6272 16474
9450 15792
6275 15545
4664 16367
6165 14150
2173 16172
4418 9699
2670 10443
3465 12331
6401 15366
7908 10283
1729 17362
1202 1...

output:

3

result:

ok 1 number(s): "3"

Test #28:

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

input:

9617 19234
705 18762
3501 10055
4984 18074
6354 10792
7343 14140
4346 10060
2920 14019
2753 18625
4273 9853
2442 16246
6798 12520
8238 17072
1852 18366
356 16352
3423 18805
3575 18946
435 15017
5612 15487
4544 12845
1152 19083
6348 9970
6452 16436
2647 9621
2839 18182
5972 12102
9467 10546
6738 1348...

output:

2

result:

ok 1 number(s): "2"

Test #29:

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

input:

9780 19559
2541 17344
1313 13484
3367 17132
6057 16121
7786 17783
7780 13534
8271 17349
3337 18400
8036 16808
7701 15270
7226 11672
7625 13075
2643 14066
5599 17154
9001 13147
1329 10549
6037 16490
7019 15139
8675 18800
3585 16157
1978 15454
1790 16123
7291 9854
6650 17016
5882 14520
7144 18976
30 1...

output:

3

result:

ok 1 number(s): "3"

Test #30:

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

input:

9943 19886
3308 17792
8106 12252
7161 18801
9175 19384
3212 10691
3355 11937
8375 17437
5610 16105
7072 12924
9529 11530
493 19415
5314 15094
636 12795
7631 12467
8902 11281
9549 14694
637 12844
9236 10841
3934 11900
530 10349
116 12767
8100 16836
834 19494
5125 17316
4453 10660
5523 17230
6448 1685...

output:

2

result:

ok 1 number(s): "2"

Test #31:

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

input:

9807 199985
7623 19300
9178 14028
5000 18373
4206 15902
5964 14283
4648 14084
6982 14988
1863 15411
2257 11432
501 15194
4366 13800
367 10745
8417 17893
4297 16634
688 15143
637 13964
1956 16506
939 13521
7415 10906
1596 13671
8663 11882
4076 16839
6457 13186
1580 16528
4078 11007
7344 17597
7615 14...

output:

3

result:

ok 1 number(s): "3"

Test #32:

score: 0
Accepted
time: 72ms
memory: 15720kb

input:

9807 199987
7151 18305
3142 18146
2075 17526
7887 15019
1011 17093
2843 14230
4427 13297
6841 18143
9637 12229
9451 14775
4083 12286
9716 11744
7112 12037
6507 12292
1198 13987
498 18172
6088 10200
220 12089
3132 10121
9308 15996
4116 16123
7855 14820
5282 17334
5343 13097
5040 14766
5599 13198
3045...

output:

2

result:

ok 1 number(s): "2"

Test #33:

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

input:

9807 199987
5246 14655
3145 18938
336 16437
1450 11493
3038 17947
599 19059
6906 10672
3506 17363
6748 12223
227 13127
8946 15194
2509 13722
8143 12579
4733 10238
8390 12801
4008 15669
9764 17413
9353 10045
5291 19219
49 19552
6027 12930
1703 19371
7770 15280
3155 10814
1239 15175
854 11389
7790 981...

output:

3

result:

ok 1 number(s): "3"

Test #34:

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

input:

9807 199989
1775 17474
9530 15029
6448 10386
7658 15002
3969 17818
6840 17354
4812 10320
931 18485
5479 16685
2305 10860
9126 12045
6366 17294
405 15334
4209 18046
4070 16206
6870 12933
7794 15852
1989 10454
9692 14681
759 9962
2192 15214
377 12216
5874 13742
5478 10762
412 16421
6966 18201
8340 147...

output:

2

result:

ok 1 number(s): "2"

Test #35:

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

input:

9807 199990
2835 17190
88 10239
4104 17147
7194 13179
9550 11899
426 13977
2156 17184
3496 19413
5224 16316
5020 10120
4976 14314
5764 11864
5937 15040
8558 16102
6072 12961
3745 13045
6977 14225
7670 14954
9035 18439
880 18184
6702 14006
7647 14714
948 13879
6379 15287
8457 17757
3795 13201
2288 15...

output:

2

result:

ok 1 number(s): "2"

Test #36:

score: 0
Accepted
time: 96ms
memory: 15840kb

input:

9807 199990
7649 17242
412 15046
7098 9900
6417 12553
6137 17750
9302 11416
2818 11889
3672 14595
7265 12807
3886 9861
400 11473
7293 10515
4913 11457
2598 19423
1073 18141
1651 15841
214 18977
8983 19367
2076 11810
4783 15800
3347 14769
3889 13021
4467 11023
7495 19092
5249 12487
3153 14098
4086 11...

output:

3

result:

ok 1 number(s): "3"

Test #37:

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

input:

9807 199992
8603 14486
6705 16938
4144 12617
3881 10429
8147 19520
8574 18361
5612 19149
7766 16027
8619 18768
408 13938
4129 16821
1567 16481
9167 15198
9511 15081
5563 15612
1241 17710
3957 19199
9391 18858
2627 16321
9407 18980
9497 13953
7328 17834
6719 16480
7740 14799
8698 17126
2581 12827
600...

output:

2

result:

ok 1 number(s): "2"

Test #38:

score: 0
Accepted
time: 97ms
memory: 15836kb

input:

9807 199993
6493 16838
5887 14883
9234 11202
219 15544
1664 15259
1842 14078
8035 10165
6086 19433
3355 14155
6555 11898
3952 15947
4810 16140
913 14492
1363 18476
2151 14629
343 14083
6103 17141
7912 14445
2998 14214
5808 18519
2783 15705
5534 17630
5482 18159
5880 12061
8103 16988
5921 14568
47 13...

output:

2

result:

ok 1 number(s): "2"

Test #39:

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

input:

9807 199993
1854 12702
3634 13379
3763 10887
2488 18349
1516 15539
7278 12788
843 16278
4304 15696
7810 16340
2928 15041
4080 14999
4527 14733
2361 16048
7023 11550
315 18104
7316 18325
2007 15850
1678 15862
6711 14972
2582 11370
9191 13402
155 18503
7417 11729
6438 15069
7854 12851
6193 11072
2238 ...

output:

3

result:

ok 1 number(s): "3"

Test #40:

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

input:

9807 199995
2336 13942
6946 15960
6305 16858
8851 10262
8234 10066
1899 17058
9358 11657
8252 15659
368 12916
3112 11860
4520 12726
805 19289
9448 11630
3414 11995
7834 16131
1723 19182
26 11812
8369 10266
731 10587
2817 14620
1395 16416
3529 12124
2407 18857
1945 11246
9779 18864
2899 11510
9190 10...

output:

2

result:

ok 1 number(s): "2"

Test #41:

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

input:

9807 199995
5319 15364
2503 19528
284 16536
8070 16974
1361 13751
1728 18544
4195 16286
2553 16394
2093 14700
7483 13705
9785 19593
7101 17303
8734 15386
6011 10584
2181 19201
2853 17903
2130 18254
1941 15393
5789 16753
6343 10304
2046 17805
5526 10673
2184 16623
1548 11798
5541 9962
542 16466
6329 ...

output:

3

result:

ok 1 number(s): "3"

Test #42:

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

input:

9807 199997
6626 10577
7420 17996
4902 10063
8809 16140
5802 10984
7799 13282
9293 10727
7625 10137
8888 15767
3794 12978
7789 12973
1789 14356
6957 18928
6464 18281
3698 14691
7769 14790
1487 15896
8600 13867
813 13951
7916 12549
6776 14908
1206 17632
9513 16386
216 15208
6409 13614
1861 14685
841 ...

output:

2

result:

ok 1 number(s): "2"

Test #43:

score: 0
Accepted
time: 99ms
memory: 15692kb

input:

9807 199997
4844 18982
2490 17994
5340 13710
9703 18938
6661 11372
7902 14822
4571 10708
80 14011
4626 17349
489 19486
6441 16354
8956 17217
7128 19377
8164 11607
3297 17699
9669 11468
5296 11602
2032 11908
6858 19087
4013 17243
8878 16245
7452 14182
443 16360
4210 19596
5671 15590
9713 15419
6940 1...

output:

3

result:

ok 1 number(s): "3"

Test #44:

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

input:

9807 199998
6137 16834
391 15169
4582 14850
5682 18125
3119 13919
3414 11909
7167 18563
8512 19454
4521 18453
9114 15340
3203 13249
7092 15073
8493 14044
2840 11535
4287 11208
1774 16150
8256 18590
8773 10220
6425 10633
5042 16196
5975 14657
4630 16271
4773 13607
9796 17862
4308 12491
647 17508
6371...

output:

3

result:

ok 1 number(s): "3"

Test #45:

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

input:

9807 200000
1964 11910
7583 17403
753 19556
5999 15729
829 10450
8801 12350
3986 12685
8072 13558
1969 12186
8495 17946
9088 16863
3351 14324
2459 18198
6081 14715
4494 14760
6288 15164
4056 13337
2921 16938
2822 13286
9638 19560
3829 10189
117 16109
1182 17990
4089 11048
6863 13978
4499 9927
8438 1...

output:

2

result:

ok 1 number(s): "2"

Test #46:

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

input:

10000 21000
6801 15065
7499 10384
3436 14304
6277 12871
1867 17863
4168 19259
6106 17303
3503 12792
2801 10493
3255 13138
3302 19124
5859 17722
6174 12365
6392 19073
4753 18255
2952 15560
2173 12114
7174 10724
4275 12474
5599 11731
2190 16648
7953 17970
2690 16566
2803 17429
24 17571
2529 10482
6324...

output:

2

result:

ok 1 number(s): "2"

Test #47:

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

input:

10000 21001
5146 18848
5581 16508
2980 13068
7967 10914
55 12129
202 11559
7654 13297
4434 19191
6135 14483
1517 12946
9772 14572
2424 15485
6329 17573
8822 18124
3013 13146
8719 10622
9898 13681
9682 14354
2460 10937
3485 16020
4684 15457
4016 16276
2426 15880
7590 18750
1034 19686
619 13421
5731 1...

output:

3

result:

ok 1 number(s): "3"

Test #48:

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

input:

10000 21002
1001 13684
3854 12966
1467 13967
8191 18901
1247 12910
5930 13251
3853 13770
3359 15565
7064 18252
8349 14607
5922 19200
1333 17601
505 19788
9177 14929
5124 16247
3404 13316
827 19989
2500 14986
5403 13343
6322 13598
1651 19260
7113 14502
4121 19647
6753 10829
1013 10091
2103 18114
6665...

output:

3

result:

ok 1 number(s): "3"

Test #49:

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

input:

10000 21003
5639 12237
5839 13390
4045 17935
5594 12067
5543 18196
2851 14828
2669 14591
3004 16802
1092 14960
7235 14077
5153 13759
1287 19597
9488 11677
4815 14924
8283 17784
5058 11323
8029 10008
4176 14177
8608 17740
6452 14086
4486 13673
1540 11288
3411 14769
8550 16700
6849 19025
7601 13066
26...

output:

3

result:

ok 1 number(s): "3"

Test #50:

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

input:

10000 21004
1906 14828
1262 17743
5122 11727
9481 13339
7878 11881
6213 18971
1306 18199
8545 10596
280 13474
8535 16077
5171 12602
8061 16391
4138 15455
690 19429
1161 18288
342 10897
3000 13235
6237 12125
7482 17852
1356 17206
2275 10778
6969 11193
5184 18332
5892 12367
4746 14346
2356 15429
1159 ...

output:

3

result:

ok 1 number(s): "3"

Test #51:

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

input:

10000 21005
651 10388
5128 18418
279 11233
6781 14069
3718 15956
38 17087
344 15919
72 11180
1207 11215
3429 12364
5632 14661
5945 15686
6600 11654
7798 18299
1132 19417
1782 11586
8522 16652
8205 19675
5402 11055
4448 16114
2811 19403
1990 15606
4343 13060
2374 19650
1777 18958
7613 17760
6863 1585...

output:

2

result:

ok 1 number(s): "2"

Test #52:

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

input:

10000 21006
2938 18777
7389 19459
9639 15800
4535 16833
9284 15702
4957 19765
5093 14159
1555 15642
6301 13222
508 11320
2392 17400
7644 10350
4411 10390
1778 17671
1243 19116
1414 12673
7034 11618
8954 12521
1960 13691
1259 17812
2337 13572
1618 13161
6682 14193
2813 15434
5936 14563
7883 16945
112...

output:

3

result:

ok 1 number(s): "3"

Test #53:

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

input:

10000 21007
4820 17550
7592 19278
576 11602
955 19780
9478 11449
9534 18294
6960 18107
1757 14154
1785 11488
6142 18195
8039 19870
6212 12131
6018 13649
5040 19473
4480 15996
7521 15655
4994 17978
6730 12644
1555 14521
9135 15721
3292 11640
2925 17475
2274 19510
6673 12854
6102 13016
4106 15353
5007...

output:

3

result:

ok 1 number(s): "3"

Test #54:

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

input:

10000 21008
7682 11085
2520 17914
10000 10559
4967 10201
6520 12679
1656 13690
3852 16591
7010 13741
3271 18376
2569 10432
6553 12348
9143 18830
6728 15914
8858 19116
5273 17967
6703 18202
421 13156
3183 17768
6019 11571
9209 16748
710 16794
5914 17028
8204 17535
8863 18440
3840 16997
5357 17669
188...

output:

3

result:

ok 1 number(s): "3"

Test #55:

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

input:

10000 21009
5794 19668
4860 11747
3454 17696
807 19829
4172 15259
2787 17094
842 17821
473 13182
6648 19599
4006 13669
8573 18381
3033 10159
9222 16514
9534 14555
4726 16710
7534 17974
7700 18129
2878 12666
2896 11772
6435 14256
5677 10793
7626 19655
2965 18750
9854 19100
2197 14170
4508 10472
5130 ...

output:

3

result:

ok 1 number(s): "3"

Test #56:

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

input:

10000 21010
6377 17588
2492 13007
9871 18611
4247 10253
4520 11050
4758 13394
7753 19393
1924 14829
271 15604
6243 15867
3104 14129
9642 14546
7450 10425
8137 12064
5305 15894
3861 10567
5074 16154
1090 10109
861 19242
9548 16027
7383 11401
8451 15786
5390 18807
7194 13326
5520 11350
8075 13120
1139...

output:

3

result:

ok 1 number(s): "3"

Test #57:

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

input:

10000 21011
725 10671
3262 13760
5878 11883
2507 13719
5398 15700
5893 16891
5968 18036
1816 11171
5373 19945
268 15046
827 13546
8963 18702
5255 10163
7912 11853
741 12540
4142 12872
9610 17716
9886 10735
2463 14028
2023 10197
5279 17610
2425 11769
2170 19380
3438 11204
7849 14750
8179 15512
778 12...

output:

3

result:

ok 1 number(s): "3"

Test #58:

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

input:

10000 21012
537 16428
4840 16895
2216 17708
4678 11421
7121 12427
9838 17807
8884 17874
5828 18700
9096 16385
5617 18056
968 18530
4124 18855
9042 13725
4083 15309
4763 17990
8530 14417
3729 12377
9870 10843
4782 17778
1852 19580
3300 12410
7982 11287
8121 11172
7828 12924
8940 18213
9515 11886
8614...

output:

3

result:

ok 1 number(s): "3"

Test #59:

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

input:

10000 21013
3322 19395
2732 19759
2562 19028
7569 10020
7135 16496
5590 13087
7036 17109
9773 14745
1048 15119
334 18638
6594 15776
8353 12921
3100 19305
673 16271
109 19352
9633 13882
1977 11319
3557 16222
5056 16297
5683 12314
3318 10245
7514 12440
9500 12615
1036 12847
5925 12203
369 17131
4299 1...

output:

3

result:

ok 1 number(s): "3"

Test #60:

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

input:

10000 21014
2091 11227
9909 11336
3310 19119
3682 19091
434 12850
9999 17651
9451 17805
1544 19647
2768 19840
1524 10383
8008 15659
9797 12851
9031 15877
2945 11739
5689 14879
5811 16597
158 12423
602 12719
1779 15860
717 12049
4496 13809
297 11659
5805 10253
1459 17734
3217 12029
3063 10928
6967 16...

output:

2

result:

ok 1 number(s): "2"

Test #61:

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

input:

10000 21015
4733 10981
9191 17977
8292 12213
9244 14467
7863 15312
7568 19935
5571 19928
1263 11015
1833 14178
9912 13660
2567 18668
3563 12461
5789 12204
9497 13250
8699 13181
2246 11373
7125 15859
8408 13951
2923 15200
290 11550
6192 14899
7236 18872
3994 10281
6701 14722
8756 18116
2957 14752
228...

output:

2

result:

ok 1 number(s): "2"

Test #62:

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

input:

10000 21016
8674 18657
8310 10149
2381 10824
8771 18561
5883 17616
8985 16627
979 11699
6268 15222
6960 14705
1175 17581
3918 15125
8726 15804
9400 15727
160 18114
9975 12340
176 19094
4577 16697
6083 15166
4442 14131
1336 13830
3944 11954
2418 14024
964 17362
4053 16785
7419 14655
2194 17356
2455 1...

output:

3

result:

ok 1 number(s): "3"

Test #63:

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

input:

10000 21017
7075 17393
6316 14561
1864 10766
2522 19084
1652 14146
3781 19796
5899 17712
8107 11985
8229 13012
9174 13841
5334 16146
8212 19182
6388 18330
3372 10587
9424 16158
4316 11885
6897 11904
5426 15546
9319 13543
756 12339
6414 18297
3619 18787
8601 17215
9318 12882
9366 10641
8436 12390
958...

output:

3

result:

ok 1 number(s): "3"

Test #64:

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

input:

10000 21018
9666 14574
9009 10119
3588 16806
8204 12022
4314 10425
7627 13683
9565 12744
334 15111
9426 11509
7855 15553
8502 12016
5137 11767
4167 19368
2987 14747
4600 15577
1137 18038
473 19654
9154 13463
6161 18516
7816 11220
1814 19399
7928 11134
9696 11657
1196 14432
6799 10185
5042 12450
4641...

output:

3

result:

ok 1 number(s): "3"

Test #65:

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

input:

10000 21019
7336 18004
5913 15656
1083 17346
6514 13099
859 18388
7439 11870
4140 19177
1560 18634
9549 13243
5534 12321
4384 15849
7768 19987
4138 19461
9100 10821
3769 13275
751 19670
7947 18256
9443 14873
4591 19115
4697 10620
359 19388
129 13573
5290 14658
6324 12396
5198 14061
1212 13423
5098 1...

output:

3

result:

ok 1 number(s): "3"

Test #66:

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

input:

10000 21020
9967 17930
2509 19673
1163 10198
7885 12955
8409 14492
1090 11695
7858 14706
6463 12113
5185 15075
4731 14281
7676 19993
6018 15727
2964 19389
630 10817
6469 13517
5739 16534
2904 15314
3507 19118
5803 12086
8539 19616
5521 13973
4574 12731
7090 19677
1965 16206
4805 10717
3881 12305
835...

output:

2

result:

ok 1 number(s): "2"

Test #67:

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

input:

10000 22000
8857 11023
247 18085
5823 13749
2363 17952
9110 14102
2174 16653
1600 17260
4708 17902
9340 19724
9014 17000
5696 17303
6682 13088
2531 18272
9724 12520
3805 11564
2349 19800
7659 15947
1742 13442
2100 17483
1377 10177
4632 13038
8010 19035
5632 15150
564 19913
5899 16948
8865 14034
8489...

output:

3

result:

ok 1 number(s): "3"

Test #68:

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

input:

10000 22001
2189 13989
9696 12515
8537 18125
3280 19137
8320 15016
22 16038
8387 17150
8389 10163
7237 19326
3621 18637
1588 10157
6116 11947
5844 12570
1794 12648
2495 16797
5258 12986
2152 11629
6474 15937
7747 14742
4503 16393
7822 15620
7095 13201
2142 10211
609 11520
583 16040
8042 11622
8583 1...

output:

2

result:

ok 1 number(s): "2"

Test #69:

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

input:

10000 22002
8198 12237
9637 15665
7133 16437
3217 12090
6384 14192
3874 15445
1842 13474
6388 15021
5260 12745
7457 16196
8262 16558
2702 17743
1805 19089
3994 16105
7288 14944
3232 16933
1439 16798
5051 18589
4972 12320
9436 12177
5729 11326
2627 10079
9019 15045
1635 15353
4548 15126
7752 13934
93...

output:

2

result:

ok 1 number(s): "2"

Test #70:

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

input:

10000 22003
7561 11493
1246 15821
4950 15450
8460 18429
6677 19576
2650 10009
2538 16756
9183 18064
8416 11113
4045 10834
6313 13959
9375 13158
6276 18807
8750 19467
1805 19043
148 16728
7834 12604
4834 11146
1283 18299
5376 19589
5923 11289
4102 19621
9926 12286
7080 16872
9652 19681
7848 19474
271...

output:

3

result:

ok 1 number(s): "3"

Test #71:

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

input:

10000 22004
8961 13843
9335 18218
307 18271
1465 10124
3558 16531
1802 17386
7574 13702
9510 16269
9035 18694
4180 19865
5051 18610
8573 13167
2656 15391
3233 14687
5955 17726
5187 11692
779 13517
2714 12044
2988 15797
7320 19270
7509 18293
243 10288
1454 13355
6599 10835
2457 10410
5258 13800
5612 ...

output:

2

result:

ok 1 number(s): "2"

Test #72:

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

input:

10000 22005
3814 10801
1558 11187
5376 17913
9638 16161
9275 10805
6029 19549
2525 16256
3003 11523
2533 15153
4713 15754
8279 19209
5753 18409
7620 19586
3323 13975
2777 15351
3084 19764
3474 18923
5767 11027
6797 13597
419 11492
9454 12885
4177 17211
1525 16327
3225 16148
3086 17632
648 10938
3783...

output:

2

result:

ok 1 number(s): "2"

Test #73:

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

input:

10000 22006
8428 17848
5021 15488
8888 14481
8748 16370
2365 12140
8219 12573
8546 16873
9258 19173
9938 10946
1434 19881
5962 11379
9550 11445
9050 19419
834 12391
3793 13867
1833 16860
3243 11490
2229 10388
8485 10340
3326 19804
4807 12652
2728 11644
2052 12326
1934 14344
8461 10608
6441 16430
295...

output:

3

result:

ok 1 number(s): "3"

Test #74:

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

input:

10000 22007
7935 12822
4709 16023
1356 11327
6000 18589
8899 12240
6838 10129
4747 13215
9739 18824
9551 12047
7149 16956
6007 15058
8842 16263
3319 17798
6683 14473
8397 14715
1505 18009
3572 17546
6596 12592
2491 16030
6089 13337
6302 12831
6801 10443
6919 11521
4881 12095
5989 17920
123 12537
141...

output:

3

result:

ok 1 number(s): "3"

Test #75:

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

input:

10000 22008
7393 15144
4680 11383
9115 14416
2483 10797
9062 14332
5080 18974
1651 16067
6221 16789
5743 13548
7208 18099
8106 13909
665 12133
3977 14071
4524 18836
1217 15601
9956 14319
3527 15588
7828 17032
6233 16944
2285 18849
8984 18371
335 16767
7157 15787
7723 10348
4625 14509
9212 18002
8632...

output:

2

result:

ok 1 number(s): "2"

Test #76:

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

input:

10000 22009
1981 11600
63 13605
9570 16566
3599 16629
8019 13685
3116 16098
6028 11168
1071 15339
4228 10078
3872 16549
786 13524
7273 13590
9410 19766
2461 19278
5279 17800
6546 16792
3832 18734
5681 11745
5640 15840
3865 10805
4071 17544
9157 17952
6493 10328
1870 16076
9758 10862
7179 19048
8356 ...

output:

3

result:

ok 1 number(s): "3"

Test #77:

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

input:

10000 22010
3068 14071
9339 11403
3861 10310
7987 13055
3174 17755
12 13431
6088 14178
2162 14118
5325 15892
5207 12299
6288 16991
5907 18149
3737 18933
3877 18186
4393 13905
3578 13952
1518 11028
5349 19728
5829 11552
5316 13188
6676 16069
8226 11284
3548 16619
4771 18845
2143 18307
2842 15011
6476...

output:

2

result:

ok 1 number(s): "2"

Test #78:

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

input:

10000 22011
39 11948
1147 15638
3374 10345
9478 14885
2975 17229
7429 19771
3664 12718
4031 19087
5547 17055
8578 17604
4496 17100
310 16222
7865 17896
4957 17515
925 17015
250 10203
980 14613
3025 11028
9552 13935
6133 16989
6772 14652
9564 11784
395 13227
7289 11678
369 17556
7464 10864
1382 12062...

output:

3

result:

ok 1 number(s): "3"

Test #79:

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

input:

10000 22012
8385 15208
211 10548
9162 11497
5004 17827
3776 19286
9338 11940
6148 19496
1323 15031
3717 18288
2955 19775
2513 16646
4328 15972
6165 13492
2528 17614
3659 19925
9492 18765
169 17386
7596 15330
1322 11616
260 11069
128 10843
7155 15081
6960 19605
9771 10158
5415 16173
5710 19624
1652 1...

output:

2

result:

ok 1 number(s): "2"

Test #80:

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

input:

10000 22013
1484 19893
1516 13227
4198 13190
2534 15235
6636 14442
7114 19604
2744 15578
3124 18321
1914 17771
979 18631
6723 17722
2796 15630
642 12455
2616 16153
9461 13475
6705 13848
9236 19272
5915 15451
2405 11397
5446 16699
7197 14494
202 18305
2343 12599
4941 14569
9504 19527
6901 18296
1466 ...

output:

2

result:

ok 1 number(s): "2"

Test #81:

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

input:

10000 22014
9446 17814
2835 17983
6301 18353
2754 10470
6183 12664
9603 12035
4715 13197
2014 18682
5126 19787
7238 12489
2176 11548
2341 15724
4083 12410
6529 13695
4276 10828
8489 15348
4176 12551
6228 19506
3044 11076
4179 18809
8219 15336
7317 13945
4439 17764
1405 13994
5625 14183
6554 10475
36...

output:

2

result:

ok 1 number(s): "2"

Test #82:

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

input:

10000 22015
2457 18176
2486 18582
4478 13462
6584 11855
7614 16554
5502 12871
4473 13800
3123 14838
7306 12344
6775 15719
7686 12831
2629 10897
4693 19257
4267 16290
6223 12901
1779 15281
7895 18762
5572 11401
4007 15617
9446 14617
7254 17739
5812 11740
5515 18928
9068 18522
9394 10348
2497 17957
14...

output:

3

result:

ok 1 number(s): "3"

Test #83:

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

input:

10000 22016
6877 12005
5833 16527
2226 13561
5467 14597
4160 19196
6001 10814
9670 15871
3553 14025
2470 10799
7780 12066
3435 16292
3934 19950
9707 11464
5389 10909
9567 11168
966 16821
8343 12779
6308 15977
2023 11804
8131 12290
6127 15063
684 10974
9886 10492
1484 14419
8582 14366
5266 18860
9971...

output:

2

result:

ok 1 number(s): "2"

Test #84:

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

input:

10000 22017
1504 12277
9705 15478
7053 15263
1383 16059
8007 11987
6712 17351
9744 18415
1932 10892
5256 18372
426 17163
2381 17603
1615 14087
4389 18103
5081 12496
5564 16124
5858 18557
9736 10743
1790 13727
52 14909
7372 10507
2493 13621
9759 17468
1697 10603
6294 12869
1137 12340
4674 16790
1836 ...

output:

3

result:

ok 1 number(s): "3"

Test #85:

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

input:

10000 22018
2093 12612
9747 15119
5133 12121
8143 14611
2659 14692
4231 17638
4662 14055
4236 16397
5829 10714
7724 12648
696 19786
3725 19881
9135 18646
5557 18865
1462 12588
7406 10427
8038 17246
2881 12557
6538 10814
9097 17119
3309 12531
9672 14213
7612 16362
6612 17092
6925 14785
8668 17954
558...

output:

2

result:

ok 1 number(s): "2"

Test #86:

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

input:

10000 22019
3819 15544
3638 18476
5725 11312
387 15877
4919 11476
6501 17744
5258 14527
9256 14965
1773 10505
6514 14193
8848 19495
6214 15498
3863 12739
26 16878
9331 13354
752 16806
1002 15906
3167 10186
1146 15109
3441 17809
9845 15777
2864 19799
9795 18436
9265 15892
8094 18312
5785 10574
8133 1...

output:

2

result:

ok 1 number(s): "2"

Test #87:

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

input:

10000 22020
6992 11044
2101 10752
5093 11910
4942 12775
1009 18170
3304 13310
8774 11869
9396 12660
7386 17718
7875 10875
1698 18752
8478 15139
9942 10764
2727 10098
2708 13282
4196 14060
3904 12172
3608 10733
7867 14047
888 10161
7143 17137
5027 19988
4841 15245
7884 14754
3627 15880
861 16567
7417...

output:

2

result:

ok 1 number(s): "2"