QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#319348#4829. Mark on a Graphduongnc0000 2ms4360kbC++205.9kb2024-02-02 14:45:442024-02-02 14:45:45

Judging History

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

  • [2024-02-02 14:45:45]
  • 评测
  • 测评结果:0
  • 用时:2ms
  • 内存:4360kb
  • [2024-02-02 14:45:44]
  • 提交

answer

/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/

#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define i64 long long
#define pb push_back
#define ff first
#define ss second
#define isz(x) (int)x.size()
using namespace std;

const int mxN = 2e5 + 5;
const int mod = 1e9 + 7;
const i64 oo = 1e18;

// https://i11www.iti.kit.edu/extra/publications/sw-fclt-05_t.pdf
// O(n + m * sqrt(m)) process() calls for graphs without loop or multiedges
void find_3_cycles(int n, const vector<array<int, 2>> &edge, auto process){
    int m = (int)edge.size();
    vector<int> deg(n), order, pos(n);
    vector<vector<int>> appear(m + 1), adj(n), found(n);
    for(auto [u, v]: edge) ++ deg[u], ++ deg[v];
    for(auto u = 0; u < n; ++ u) appear[deg[u]].push_back(u);
    for(auto d = m; d >= 0; -- d) order.insert(order.end(), appear[d].begin(), appear[d].end());
    for(auto i = 0; i < n; ++ i) pos[order[i]] = i;
    for(auto i = 0; i < m; ++ i){
        int u = pos[edge[i][0]], v = pos[edge[i][1]];
        adj[u].push_back(v), adj[v].push_back(u);
    }
    for(auto u = 0; u < n; ++ u) for(auto v: adj[u]) if(u < v){
        for(auto i = 0, j = 0; i < (int)found[u].size() && j < (int)found[v].size(); ){
            if(found[u][i] == found[v][j]){
                process(order[u], order[v], order[found[u][i]]);
                ++ i, ++ j;
            }
            else if(found[u][i] < found[v][j]) ++ i;
            else ++ j;
        }
        found[v].push_back(u);
    }
}

template<bool Enable_small_to_large = true>
struct disjoint_set{
    int n, _classes;
    vector<int> p;
    disjoint_set(int n): n(n), _classes(n), p(n, -1){ }
    int make_set(){
        p.push_back(-1);
        ++ _classes;
        return n ++;
    }
    int classes() const{
        return _classes;
    }
    int root(int u){
        return p[u] < 0 ? u : p[u] = root(p[u]);
    }
    bool share(int a, int b){
        return root(a) == root(b);
    }
    int size(int u){
        return -p[root(u)];
    }
    bool merge(int u, int v){
        u = root(u), v = root(v);
        if(u == v) return false;
        -- _classes;
        if constexpr(Enable_small_to_large) if(p[u] > p[v]) swap(u, v);
        p[u] += p[v], p[v] = u;
        return true;
    }
    bool merge(int u, int v, auto act){
        u = root(u), v = root(v);
        if(u == v) return false;
        -- _classes;
        bool swapped = false;
        if constexpr(Enable_small_to_large) if(p[u] > p[v]) swap(u, v), swapped = true;
        p[u] += p[v], p[v] = u;
        act(u, v, swapped);
        return true;
    }
    void clear(){
        _classes = n;
        fill(p.begin(), p.end(), -1);
    }
    vector<vector<int>> group_up(){
        vector<vector<int>> g(n);
        for(auto i = 0; i < n; ++ i) g[root(i)].push_back(i);
        g.erase(remove_if(g.begin(), g.end(), [&](auto &s){ return s.empty(); }), g.end());
        return g;
    }
};

int n, m;
vector<array<int, 2>> G;
map<int, int> adj[1005];
int indeg[1005], av[1005];

void add_edge(int u, int v) {
    ++indeg[u], ++indeg[v];
    adj[u][v]++, adj[v][u]++;
}

bool check(vector<int> &pos) {
    for (int i = 0; i < isz(pos); ++i) {
        for (int j = i + 1; j < isz(pos); ++j) {
            if (adj[pos[i]].find(pos[j]) == adj[pos[i]].end())
                return true;
        }
    }
    return false;
}

void solve() {
    cin >> n >> m;
    disjoint_set dsu(n);
    iota(av + 1, av + n + 1, 1);
    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;
        add_edge(u, v);
        // dsu.merge(u, v);
        // G.push_back({u, v});
    }
    sort(av + 1, av + n + 1, [&](int x, int y) {
        return indeg[x] > indeg[y];
    });
    int cnt = 0;
    vector<int> pos;
    vector<pair<int, int>> op;
    for (int i = 1; i <= 10; ++i) if (indeg[av[i]] % 2) {
        pos.emplace_back(av[i]);
    }
    while (isz(pos) > 1 and check(pos)) {
        int woo1 = -1, woo2 = -1;
        for (int i = 0; i < isz(pos); ++i)
            for (int j = i + 1; j < isz(pos); ++j)
                if (adj[pos[i]].find(pos[j]) == adj[pos[i]].end())
                    woo1 = i, woo2 = j;
        add_edge(pos[woo1], pos[woo2]);
        op.emplace_back(pos[woo1], pos[woo2]);
        vector<int> npos;
        for (int i = 0; i < isz(pos); ++i) if (i != woo1 and i != woo2) npos.emplace_back(pos[i]);
        pos = npos;
    }
    for (int idx : pos) {
        for (int j = n; j >= 1; --j) if (adj[idx].find(av[j]) == adj[idx].end()) {
            add_edge(av[j], idx);
            op.emplace_back(av[j], idx);
            break;
        }
    }
    if (isz(op) == 0) {
        cout << "ok" << endl;
        return;
    }
    cout << "mark" << endl << isz(op) << endl;
    for (auto [u, v] : op) cout << u << " " << v << endl;
    // for (int i = 0; i < 10; ++i) cout << indeg[av[i + 1]] << " \n"[i == 9];
    // assert(*max_element(indeg, indeg + n) <= 5);
    // cout << dsu.classes() << endl;
    // find_3_cycles(n, G, process);
}

signed main() {

#ifndef CDuongg
    if(fopen(taskname".inp", "r"))
        assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout));
#else
    freopen("bai3.inp", "r", stdin);
    freopen("bai3.out", "w", stdout);
    auto start = chrono::high_resolution_clock::now();
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1; //cin >> t;
    while(t--) solve();

#ifdef CDuongg
   auto end = chrono::high_resolution_clock::now();
   cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
   cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
   cout << "Check array size pls sir" << endl;
#endif

}

详细

Test #1:

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

input:

1000 3560
603 151
415 20
102 569
895 552
678 734
24 614
689 518
440 223
751 919
223 433
711 551
502 634
706 583
812 501
514 535
780 751
720 530
532 384
888 139
864 791
292 675
171 881
30 592
464 557
280 299
654 650
894 335
250 532
792 10
83 969
118 771
579 300
852 983
243 940
957 939
817 889
911 319...

output:

mark
3
875 366
108 611
733 310

input:

1000 3563
777 626
222 295
811 665
534 338
682 101
833 706
950 155
656 841
184 95
383 221
259 86
815 771
37 355
759 167
402 763
582 250
950 401
802 224
974 277
521 380
368 12
676 977
920 351
831 643
511 688
553 125
506 102
757 70
736 226
733 87
956 373
600 53
201 580
844 267
14 201
583 975
557 937
16...

output:

ok

result:

ok all right

Test #2:

score: 100
Accepted
time: 1ms
memory: 3908kb

input:

1000 2000
457 335
160 497
464 992
892 255
853 3
308 301
970 363
541 299
89 418
425 128
626 827
603 854
484 874
755 295
607 483
798 552
356 850
320 357
254 940
675 901
168 525
301 636
520 555
773 910
343 701
889 966
218 529
909 950
71 64
682 284
424 138
721 792
670 544
386 72
654 909
725 235
592 437
...

output:

mark
1
861 727

input:

1000 2001
181 711
426 320
503 386
377 826
97 233
231 792
993 1
403 152
381 532
554 117
541 72
291 182
962 916
765 649
252 673
756 751
529 178
731 827
39 689
541 268
139 620
379 851
727 755
622 628
341 884
813 945
564 74
863 90
99 543
25 858
298 450
411 738
758 705
770 529
414 78
838 977
956 965
50 9...

output:

ok

result:

ok all right

Test #3:

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

input:

1000 5000
449 632
597 26
701 322
249 190
411 770
666 596
989 995
112 861
445 818
544 659
24 680
739 593
344 439
193 932
600 526
574 869
216 918
716 793
259 686
555 993
255 578
659 271
328 524
729 672
39 771
241 866
27 790
417 109
56 403
338 299
387 232
280 306
589 794
833 419
900 802
54 697
539 807
...

output:

mark
4
396 350
593 202
566 748
869 539

input:

1000 5004
258 506
563 742
458 36
208 588
178 845
559 170
361 150
350 788
619 34
977 914
578 699
634 106
213 340
156 570
83 564
647 61
128 762
345 143
821 596
976 995
155 835
60 376
334 471
116 10
467 792
494 48
464 286
956 247
726 21
405 143
612 419
42 981
693 70
407 899
285 697
256 532
649 530
240 ...

output:

ok

result:

ok all right

Test #4:

score: 100
Accepted
time: 1ms
memory: 4208kb

input:

1000 3156
347 398
792 278
754 442
413 757
391 130
636 625
207 437
81 415
47 974
887 779
524 619
379 894
868 594
653 919
29 117
123 867
632 505
648 147
130 420
495 876
637 659
882 348
462 878
282 646
398 525
419 224
926 448
305 934
855 570
396 345
774 918
336 123
502 491
984 783
845 142
790 594
754 4...

output:

mark
3
796 951
881 386
115 418

input:

1000 3159
540 43
167 499
962 403
342 814
154 900
212 990
612 516
712 963
777 715
243 539
28 441
904 773
810 843
856 38
841 423
811 609
729 7
668 435
64 931
392 925
865 396
527 503
798 64
954 311
315 976
508 855
42 940
215 161
501 674
957 617
225 869
919 879
421 610
639 127
923 58
517 216
799 671
470...

output:

ok

result:

ok all right

Test #5:

score: 100
Accepted
time: 1ms
memory: 4264kb

input:

1000 3433
634 21
789 966
541 959
213 381
366 781
107 649
747 122
336 869
222 648
833 972
929 524
712 524
744 525
568 679
634 163
901 501
56 518
128 587
720 117
208 439
860 85
852 168
934 947
34 858
520 568
408 464
232 432
999 504
71 982
957 372
570 436
281 309
410 405
521 275
554 589
4 707
498 148
5...

output:

mark
4
316 156
413 371
631 284
214 797

input:

1000 3437
976 492
771 824
416 864
904 368
376 943
665 576
49 853
251 396
313 452
899 769
437 114
649 427
593 653
514 238
606 993
685 959
722 527
837 342
121 690
919 567
307 925
776 682
505 114
31 681
474 964
669 188
505 579
565 589
743 969
157 802
671 425
441 167
190 992
410 42
947 455
49 960
97 664...

output:

ok

result:

ok all right

Test #6:

score: 100
Accepted
time: 1ms
memory: 4232kb

input:

1000 3057
985 223
432 967
405 822
845 650
893 646
599 718
754 710
333 73
392 355
895 496
200 562
816 36
457 953
9 623
889 662
482 590
249 29
689 694
185 990
285 690
12 323
611 560
903 722
476 86
105 666
441 193
695 640
36 617
840 42
80 527
977 539
606 150
384 585
784 648
919 360
157 532
568 98
995 8...

output:

mark
2
31 485
134 394

input:

1000 3059
29 48
868 224
13 300
440 290
294 719
506 107
14 443
241 921
842 25
722 560
545 503
921 572
590 27
132 790
42 458
25 364
340 372
193 518
42 660
317 815
977 433
761 633
95 970
450 626
333 585
971 732
337 771
63 271
485 551
239 366
440 279
189 644
115 949
138 624
22 995
495 460
191 934
578 21...

output:

ok

result:

ok all right

Test #7:

score: 100
Accepted
time: 1ms
memory: 3968kb

input:

1000 3085
484 405
841 443
661 315
392 941
355 558
523 394
773 929
673 840
5 707
255 610
744 58
301 794
505 33
668 533
787 945
747 810
803 115
340 900
791 909
596 418
129 491
460 698
156 233
664 502
231 465
795 486
829 102
608 212
253 344
419 557
100 421
321 793
207 302
544 479
33 916
736 129
6 156
9...

output:

mark
3
305 664
581 888
729 877

input:

1000 3088
821 665
956 248
417 787
734 95
330 953
826 533
888 479
883 619
174 625
554 613
160 480
570 952
158 636
76 223
518 617
743 937
685 728
427 52
568 778
474 293
247 977
332 533
773 219
31 664
108 860
640 186
907 603
436 948
289 874
710 197
831 963
453 369
44 843
772 765
347 200
330 595
268 65
...

output:

ok

result:

ok all right

Test #8:

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

input:

1000 4289
963 66
959 467
930 83
419 699
731 948
702 583
699 245
636 721
859 551
377 251
90 889
286 843
908 47
864 979
223 948
269 684
85 579
162 376
414 255
602 884
65 132
842 907
488 360
553 898
649 249
253 711
675 632
629 446
708 413
819 511
512 113
189 76
242 464
828 261
440 737
643 389
75 907
49...

output:

mark
2
632 783
611 963

input:

1000 4291
332 749
188 54
898 992
302 493
586 861
246 17
154 311
838 229
501 316
209 227
784 338
987 999
510 121
91 866
757 8
994 36
972 83
477 824
924 603
496 756
320 32
453 521
433 628
937 526
18 740
686 723
784 591
510 698
317 920
838 799
447 186
474 789
845 588
71 110
337 257
492 670
388 957
527 ...

output:

ok

result:

ok all right

Test #9:

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

input:

1000 4763
544 167
316 76
78 841
699 1
645 745
827 262
568 545
595 81
924 561
108 253
397 626
142 967
613 397
723 633
711 259
363 249
5 436
165 88
178 463
734 529
195 324
135 41
1000 136
215 967
371 638
588 753
542 909
633 106
537 852
111 232
303 500
892 461
868 300
772 667
40 172
956 575
613 163
933...

output:

mark
3
425 983
214 509
571 148

input:

1000 4766
450 16
910 74
103 774
597 624
185 948
625 965
921 271
347 329
156 57
747 193
936 135
594 591
22 837
259 918
762 516
500 479
444 148
161 857
680 705
58 379
897 116
415 90
917 70
78 971
976 767
429 673
66 526
667 621
847 589
37 148
173 872
965 793
396 746
688 388
214 818
820 306
687 862
93 2...

output:

ok

result:

ok all right

Test #10:

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

input:

1000 4250
747 446
769 425
773 753
217 298
217 4
514 774
752 3
905 857
532 410
224 250
367 33
29 541
809 996
76 960
25 603
532 600
518 304
546 95
735 413
312 476
83 534
157 62
170 836
668 976
244 557
972 860
828 170
975 468
677 714
800 170
530 191
216 930
242 728
318 505
269 162
579 963
769 822
171 4...

output:

mark
1
385 5

input:

1000 4251
112 370
102 703
776 233
835 409
598 303
590 999
320 874
639 193
378 512
447 83
308 365
152 512
219 36
14 309
600 242
8 847
585 656
524 394
600 888
342 188
275 604
326 920
728 164
380 74
892 31
797 986
984 629
148 404
377 353
270 344
578 582
5 848
261 174
398 338
494 140
371 94
146 199
45 2...

output:

ok

result:

ok all right

Test #11:

score: 100
Accepted
time: 1ms
memory: 3960kb

input:

1000 3336
161 745
81 702
879 347
452 553
809 32
359 925
984 783
558 366
611 89
948 530
565 496
123 348
534 986
991 511
322 407
6 878
20 897
188 150
527 440
487 333
218 572
597 575
308 684
50 780
900 451
763 785
210 682
964 992
811 537
537 167
320 133
523 899
629 732
435 281
826 405
868 567
201 858
2...

output:

mark
4
718 386
688 704
947 565
299 359

input:

1000 3340
374 704
505 741
976 541
334 161
338 863
529 120
166 728
961 763
432 952
34 757
997 947
903 519
820 520
294 110
108 967
256 659
957 285
337 937
681 518
979 589
931 88
913 533
752 222
709 505
843 608
168 502
705 49
897 312
758 572
181 928
300 162
113 469
723 195
585 934
540 513
405 713
921 5...

output:

ok

result:

ok all right

Test #12:

score: 100
Accepted
time: 1ms
memory: 4236kb

input:

1000 3482
910 881
481 989
349 262
963 679
970 752
651 210
86 339
724 310
765 410
118 619
662 351
568 148
292 61
136 385
997 772
210 735
816 310
698 649
581 313
414 280
92 872
965 925
35 930
813 29
617 210
854 940
486 479
412 644
660 623
126 85
664 327
459 165
266 113
108 206
686 660
918 536
173 366
...

output:

mark
1
333 963

input:

1000 3483
732 216
26 72
633 812
543 565
128 60
104 532
597 504
46 473
87 574
575 144
496 698
646 382
613 317
6 890
739 307
680 811
384 394
455 148
487 770
851 666
52 549
160 733
544 682
624 866
877 240
674 630
256 803
812 625
840 631
346 963
959 707
767 843
220 573
594 935
616 825
391 131
744 173
61...

output:

ok

result:

ok all right

Test #13:

score: 100
Accepted
time: 1ms
memory: 4076kb

input:

1000 2141
358 723
692 581
753 295
864 391
984 462
525 271
508 897
739 537
124 933
577 499
863 37
279 622
361 605
454 951
527 837
1 224
641 404
479 220
931 126
182 719
464 451
805 452
529 800
292 689
17 320
728 790
967 41
412 752
276 535
643 636
611 56
802 414
861 603
857 722
1000 584
435 118
266 392...

output:

mark
3
985 607
442 478
609 790

input:

1000 2144
482 327
721 271
324 265
542 340
774 998
33 221
882 886
960 447
898 211
433 35
745 399
692 986
422 376
816 821
561 879
414 613
27 223
38 338
152 849
453 625
98 796
7 425
257 760
824 441
680 49
476 761
585 315
907 925
938 131
30 914
491 113
788 961
489 597
710 34
409 587
623 686
967 308
948 ...

output:

ok

result:

ok all right

Test #14:

score: 100
Accepted
time: 1ms
memory: 3984kb

input:

1000 2950
244 361
694 442
547 577
545 866
488 207
888 997
263 45
850 200
30 927
195 510
274 582
467 158
664 667
880 573
522 986
736 375
206 326
999 940
875 609
151 161
602 673
664 200
827 579
12 190
300 249
95 502
951 317
669 243
350 841
692 572
619 302
955 999
480 891
109 779
198 893
105 442
214 14...

output:

mark
3
474 1
252 154
651 170

input:

1000 2953
350 585
754 407
289 802
501 671
458 256
116 883
867 14
370 353
816 59
543 229
222 246
204 294
666 263
995 89
208 256
257 570
433 526
293 939
181 66
840 529
60 878
916 716
984 761
343 981
724 3
367 24
462 578
262 59
414 755
113 590
535 476
1 865
22 248
279 841
15 167
771 209
725 260
482 237...

output:

ok

result:

ok all right

Test #15:

score: 100
Accepted
time: 1ms
memory: 3904kb

input:

1000 2725
336 461
575 6
961 482
496 574
134 336
671 452
172 957
633 89
909 334
222 155
90 660
201 950
436 671
726 683
487 356
536 389
107 844
403 732
550 608
607 54
718 438
960 144
710 278
398 747
152 501
86 385
34 251
309 822
773 321
329 213
897 948
356 401
290 329
278 591
683 454
122 523
729 436
4...

output:

mark
1
160 401

input:

1000 2726
826 863
860 669
482 188
461 442
496 849
962 420
832 558
899 680
933 304
876 932
6 579
49 750
506 996
166 759
563 508
331 228
210 471
707 306
89 391
16 349
161 923
496 830
591 108
534 553
220 382
489 624
969 790
385 891
900 848
69 837
478 216
455 579
539 29
37 915
554 860
316 683
143 324
33...

output:

ok

result:

ok all right

Test #16:

score: 100
Accepted
time: 1ms
memory: 3948kb

input:

1000 2812
357 725
462 948
927 875
21 284
52 197
457 876
744 315
990 255
660 522
51 971
392 275
736 77
131 216
581 438
495 271
965 111
376 89
824 363
628 13
33 585
836 144
791 404
916 588
668 243
960 335
505 368
744 264
332 893
65 320
205 81
929 44
135 224
306 351
938 505
70 927
825 634
161 492
434 1...

output:

mark
3
972 624
895 828
187 909

input:

1000 2815
548 677
425 134
295 218
332 463
514 383
894 308
900 81
922 400
176 364
59 798
403 327
873 525
996 629
187 626
804 592
99 891
353 321
597 445
745 371
788 328
63 207
321 703
446 391
83 166
347 146
938 32
740 524
279 257
898 307
172 334
672 353
863 603
224 843
172 296
897 177
214 437
205 736
...

output:

ok

result:

ok all right

Test #17:

score: 100
Accepted
time: 1ms
memory: 3992kb

input:

1000 2616
518 38
164 144
301 140
711 11
36 636
443 779
107 901
467 922
759 675
229 276
467 880
975 435
382 460
238 663
639 927
74 953
777 326
689 944
152 237
501 789
795 889
95 376
390 401
279 64
520 803
273 292
333 454
202 485
860 54
872 641
101 951
236 726
464 847
992 656
576 565
739 176
562 327
2...

output:

mark
2
412 118
301 990

input:

1000 2618
345 700
738 208
607 947
632 659
165 323
876 642
993 338
80 917
709 733
514 965
280 753
15 843
47 645
624 991
415 794
325 151
788 759
21 932
869 528
277 641
792 637
988 918
976 310
929 96
625 162
43 193
691 417
179 744
654 868
523 555
680 739
954 81
676 33
230 213
732 918
592 760
481 154
89...

output:

ok

result:

ok all right

Test #18:

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

input:

1000 4792
659 787
666 143
711 116
742 958
604 434
293 882
175 28
557 753
106 808
527 599
942 249
843 109
174 76
429 255
415 489
463 540
878 235
688 87
629 402
927 418
704 734
886 463
702 992
570 370
492 865
795 889
638 594
887 203
732 896
610 492
960 422
44 255
442 448
426 697
862 351
318 277
783 22...

output:

mark
3
592 110
35 588
548 46

input:

1000 4795
72 88
722 243
805 260
50 598
295 877
373 83
715 329
176 340
196 387
956 159
2 871
737 903
500 615
513 232
167 490
533 887
426 406
375 107
492 552
565 754
733 70
357 489
934 43
447 256
420 199
863 879
144 740
952 343
550 612
706 778
30 629
555 349
402 697
98 849
117 838
528 562
486 627
454 ...

output:

ok

result:

ok all right

Test #19:

score: 100
Accepted
time: 1ms
memory: 4300kb

input:

1000 3724
513 194
958 159
936 285
493 34
668 957
824 152
450 421
92 170
416 782
546 100
698 433
299 741
261 975
661 408
4 927
789 856
52 784
541 618
99 780
527 957
618 74
440 321
839 496
360 484
71 21
149 302
25 505
240 587
584 736
490 934
817 867
682 287
882 528
985 852
201 46
254 112
862 582
379 3...

output:

mark
2
979 737
377 824

input:

1000 3726
257 545
712 740
457 972
157 941
782 667
81 818
469 431
32 340
441 704
304 93
514 298
911 503
97 967
239 357
717 11
108 496
480 902
340 865
920 508
683 106
239 216
956 462
6 261
916 123
586 17
131 313
414 115
284 921
351 805
828 635
13 197
966 380
301 968
922 154
175 703
472 495
603 120
479...

output:

ok

result:

ok all right

Test #20:

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

input:

1000 4188
106 174
116 750
197 421
387 311
48 148
296 628
755 929
804 267
341 16
263 676
486 178
334 256
639 453
183 206
497 528
911 457
854 258
104 922
931 576
725 214
300 460
149 847
754 657
670 983
525 366
475 667
680 376
676 126
929 766
437 821
646 717
578 151
885 981
394 105
264 225
429 390
502 ...

output:

mark
2
877 158
262 654

input:

1000 4190
124 365
552 777
351 939
750 527
559 920
160 76
525 292
753 349
4 209
95 116
435 788
603 700
789 522
380 280
678 489
882 778
312 223
866 738
970 965
895 279
578 808
931 659
909 193
69 249
426 907
695 105
480 686
540 109
387 580
774 301
679 166
131 3
840 645
388 479
300 367
463 209
747 514
6...

output:

ok

result:

ok all right

Test #21:

score: 100
Accepted
time: 1ms
memory: 4252kb

input:

1000 3236
622 762
548 197
457 126
655 978
275 215
472 112
762 998
649 242
890 339
337 1
169 283
365 486
584 324
988 887
406 500
62 591
512 839
76 251
479 635
485 217
961 204
934 8
621 40
374 227
1 403
644 72
758 370
436 494
174 341
770 80
421 125
151 211
405 389
514 637
808 815
131 762
647 518
804 7...

output:

mark
3
301 322
642 415
437 247

input:

1000 3239
797 806
823 240
211 449
697 612
581 389
239 305
947 71
127 894
862 736
716 543
131 22
414 124
436 957
326 789
583 966
725 351
488 284
705 839
193 26
303 321
788 325
85 481
350 53
413 585
222 324
547 186
542 273
542 367
95 353
107 984
394 216
69 975
431 392
991 835
509 204
917 796
813 935
4...

output:

ok

result:

ok all right

Test #22:

score: 100
Accepted
time: 1ms
memory: 4032kb

input:

1000 3299
693 455
906 758
704 271
639 392
910 445
984 43
821 447
3 475
929 500
879 29
243 657
602 744
974 96
879 79
225 9
868 993
115 636
701 248
995 83
781 441
995 320
766 534
432 827
65 632
873 392
231 943
502 170
856 584
368 665
391 797
734 568
538 613
539 984
505 285
965 253
446 107
605 681
216 ...

output:

mark
2
774 474
873 300

input:

1000 3301
938 126
741 12
387 652
828 78
627 911
571 512
227 294
290 451
194 844
983 638
707 311
148 530
17 440
808 338
650 955
877 825
839 816
587 770
855 628
368 694
798 292
821 85
735 576
558 209
938 759
581 936
727 987
879 50
120 177
735 72
197 500
997 461
109 774
961 613
364 867
607 691
735 333
...

output:

ok

result:

ok all right

Test #23:

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

input:

1000 3482
45 265
363 58
385 372
365 256
659 227
700 636
954 356
708 312
24 144
103 367
797 394
779 615
596 57
546 439
622 318
344 724
27 792
286 475
286 469
581 321
191 79
457 80
357 577
559 587
63 234
982 665
838 402
931 320
724 796
645 275
254 812
283 710
75 269
991 914
888 557
214 416
316 465
197...

output:

mark
3
372 724
696 316
809 361

input:

1000 3485
186 427
612 371
891 660
864 538
497 968
491 936
679 693
864 201
46 605
107 152
559 812
147 971
381 266
944 719
27 474
908 854
779 119
334 272
468 589
148 198
615 811
809 919
929 299
407 912
236 428
217 365
333 726
953 889
146 237
443 682
657 913
230 104
153 853
97 435
616 140
460 573
512 3...

output:

ok

result:

ok all right

Test #24:

score: 100
Accepted
time: 1ms
memory: 4132kb

input:

1000 2311
97 580
515 270
609 837
243 284
715 189
980 486
853 479
235 7
253 300
207 583
282 612
456 80
486 497
503 404
74 701
64 172
583 794
570 655
901 25
14 568
485 218
621 50
253 26
433 784
533 215
134 695
278 364
879 983
690 952
198 197
725 421
95 464
927 999
104 71
752 252
553 356
187 952
38 859...

output:

mark
3
889 185
319 546
690 7

input:

1000 2314
352 855
462 672
981 153
8 103
426 470
344 569
903 148
674 805
181 180
625 109
129 469
307 645
650 7
803 437
286 930
240 100
933 748
146 992
235 494
592 6
244 376
369 211
871 106
609 12
774 39
875 536
75 610
739 885
157 343
268 825
57 219
406 525
436 622
40 654
440 205
483 369
12 914
612 41...

output:

ok

result:

ok all right

Test #25:

score: 100
Accepted
time: 1ms
memory: 4076kb

input:

1000 3896
460 688
426 709
610 203
65 902
606 471
519 789
275 370
86 879
786 822
601 948
312 884
115 372
100 491
967 601
104 750
411 830
571 626
201 132
175 126
678 756
610 712
267 770
853 475
406 479
485 471
479 953
156 968
785 918
61 114
348 147
659 495
709 716
248 599
984 20
728 726
859 759
681 10...

output:

mark
4
358 275
712 590
65 814
600 224

input:

1000 3900
742 623
861 745
673 202
367 848
894 883
586 587
775 186
180 322
14 935
976 535
72 47
962 699
98 938
811 277
487 894
310 220
241 715
114 719
766 469
311 70
203 360
765 626
86 978
573 196
756 536
517 249
607 227
938 982
589 1
994 36
365 297
1 264
788 573
317 999
957 689
7 42
168 171
651 696
...

output:

ok

result:

ok all right

Test #26:

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

input:

1000 3891
701 522
952 922
356 456
249 391
128 593
9 524
661 405
984 460
440 470
639 699
782 189
537 74
184 399
888 710
975 120
475 924
602 492
200 577
978 478
611 758
886 262
404 313
44 559
170 35
749 501
848 364
6 401
723 549
110 186
281 506
52 379
84 255
755 196
824 136
985 230
523 682
826 823
560...

output:

mark
2
110 229
451 613

input:

1000 3893
308 239
906 576
855 401
871 456
761 481
151 418
316 262
395 230
968 265
366 209
648 416
806 90
469 51
139 551
885 203
696 592
694 106
609 389
673 9
943 668
577 269
925 184
513 927
520 69
153 48
859 422
542 237
868 791
21 677
741 861
388 763
998 999
205 353
655 906
603 952
641 205
963 488
8...

output:

ok

result:

ok all right

Test #27:

score: 100
Accepted
time: 1ms
memory: 4252kb

input:

1000 3265
924 167
3 999
663 583
890 496
619 193
641 842
720 966
650 470
975 552
309 965
968 739
223 474
41 188
279 73
663 940
438 173
385 280
113 178
896 270
15 956
456 196
291 323
392 622
180 781
469 950
685 672
633 436
562 153
407 796
209 630
750 874
190 614
400 306
560 935
235 777
500 785
378 332...

output:

mark
2
93 822
890 888

input:

1000 3267
840 599
212 282
328 540
346 924
492 841
461 613
202 190
578 347
60 359
356 659
250 766
67 64
225 714
970 679
810 974
326 692
886 638
240 378
402 479
597 130
225 927
281 849
79 963
498 397
471 748
598 56
479 778
749 725
820 804
695 140
928 719
283 845
673 485
62 733
238 556
310 648
291 185
...

output:

ok

result:

ok all right

Test #28:

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

input:

1000 4070
7 484
881 280
807 812
167 913
190 699
784 415
747 45
424 328
414 997
461 463
499 437
173 675
71 525
195 736
428 593
560 602
235 557
91 265
580 422
522 212
50 326
784 938
787 256
963 883
896 902
228 953
997 406
724 753
202 646
93 118
187 777
841 254
573 651
198 821
89 615
124 443
622 120
58...

output:

mark
2
615 474
268 87

input:

1000 4072
370 139
188 415
372 852
788 793
945 841
145 964
33 131
250 810
410 234
106 136
702 46
594 861
934 406
972 967
951 669
868 713
722 81
619 522
598 759
509 796
687 279
905 218
196 536
839 223
502 324
978 610
701 635
816 708
865 594
151 808
985 787
470 624
647 42
907 618
712 958
580 999
418 62...

output:

ok

result:

ok all right

Test #29:

score: 100
Accepted
time: 1ms
memory: 4244kb

input:

1000 3135
679 441
832 386
95 753
472 452
550 725
334 216
547 305
556 805
250 217
546 555
109 827
884 984
297 80
660 821
807 403
301 250
489 275
256 342
841 435
290 873
771 188
76 424
261 377
793 458
945 925
593 432
527 275
971 222
646 49
284 713
3 37
313 181
314 122
257 969
765 89
759 537
273 857
38...

output:

mark
3
857 512
348 569
412 356

input:

1000 3138
853 905
930 978
599 172
751 672
290 682
417 18
848 839
845 328
751 1000
798 864
531 931
792 247
445 58
326 396
245 651
994 672
129 922
540 352
229 502
777 608
571 489
762 234
762 310
463 959
708 610
114 333
692 710
414 891
805 646
461 590
140 246
947 227
689 589
185 650
76 803
297 204
802 ...

output:

ok

result:

ok all right

Test #30:

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

input:

1000 4200
448 409
48 552
204 139
701 128
189 761
181 385
118 653
471 26
968 195
976 473
19 907
837 969
942 346
489 372
710 765
648 339
527 477
990 60
125 276
56 249
110 276
864 906
796 39
940 90
91 628
37 667
25 886
550 150
657 438
553 447
682 141
77 926
647 290
139 792
167 696
965 705
898 787
644 6...

output:

mark
1
965 427

input:

1000 4201
968 760
481 311
737 157
459 517
444 654
5 31
742 400
704 149
684 109
445 81
203 188
635 609
494 745
15 377
363 510
95 432
787 720
17 219
506 389
623 645
166 745
703 771
411 534
689 451
577 838
390 31
935 967
974 802
654 788
1 605
910 38
438 62
195 25
585 513
356 892
660 750
391 77
792 718
...

output:

ok

result:

ok all right

Test #31:

score: 100
Accepted
time: 1ms
memory: 4032kb

input:

1000 2992
768 684
51 962
667 28
959 894
941 636
131 80
869 468
666 543
262 235
241 428
893 839
546 428
445 949
262 763
896 402
205 644
192 650
177 921
29 488
758 527
657 817
447 872
708 323
759 927
146 982
654 973
787 923
132 163
219 813
822 144
515 188
327 452
542 32
455 122
610 461
203 303
27 766
...

output:

mark
2
939 10
426 334

input:

1000 2994
996 728
73 311
155 334
275 68
741 290
302 569
958 655
775 386
714 541
992 924
337 226
921 446
639 510
728 124
31 37
117 27
961 203
629 165
679 229
606 685
875 89
895 254
153 736
982 797
780 103
611 404
699 12
110 211
59 888
41 954
206 472
55 331
269 471
145 533
292 346
92 403
325 408
373 7...

output:

ok

result:

ok all right

Test #32:

score: 100
Accepted
time: 1ms
memory: 4076kb

input:

1000 3891
9 226
167 799
23 992
910 468
750 904
219 238
571 266
968 429
700 878
3 169
108 842
736 273
789 322
446 694
869 533
491 744
526 730
190 941
610 146
853 939
824 574
399 326
116 328
687 960
68 460
222 735
64 875
462 627
955 990
5 890
393 852
651 134
683 374
99 609
854 927
357 84
81 455
963 69...

output:

mark
4
267 929
113 446
79 546
775 595

input:

1000 3895
330 308
644 809
856 474
255 914
437 780
618 567
332 807
581 445
625 482
39 566
680 623
497 20
999 168
916 543
976 625
566 142
968 592
52 961
519 154
107 910
950 474
644 946
572 793
270 284
951 404
104 716
281 731
832 104
218 21
92 470
17 400
231 143
932 896
100 836
513 839
424 636
364 344
...

output:

ok

result:

ok all right

Test #33:

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

input:

1000 4839
721 823
946 252
516 492
460 116
126 30
65 344
134 175
802 407
634 405
799 22
808 599
433 519
711 519
30 52
457 114
41 136
668 659
743 511
155 962
436 847
671 472
549 352
688 699
167 943
467 460
292 150
801 507
559 497
890 264
565 630
672 272
15 90
869 979
853 947
119 690
501 832
285 936
34...

output:

mark
3
155 808
748 691
514 529

input:

1000 4842
591 448
280 878
531 94
305 340
63 550
632 820
980 154
377 614
539 758
528 724
922 73
925 829
206 580
426 899
948 227
935 23
626 870
344 653
728 105
582 947
43 373
442 499
190 400
16 108
746 84
370 984
207 684
723 559
711 634
467 799
953 160
928 692
353 269
230 32
656 733
193 450
861 266
69...

output:

ok

result:

ok all right

Test #34:

score: 100
Accepted
time: 1ms
memory: 3852kb

input:

1000 2034
672 408
42 15
81 165
720 365
17 795
12 752
996 718
504 262
723 214
405 139
860 837
659 586
873 356
313 426
115 550
620 942
287 815
539 518
574 531
642 428
696 628
532 548
164 371
382 434
397 223
880 826
667 805
851 587
387 528
731 649
88 252
738 790
871 539
763 587
116 818
394 292
267 380
...

output:

mark
3
113 787
476 461
540 795

input:

1000 2037
986 198
322 134
291 293
302 113
287 433
909 695
629 333
845 955
842 902
953 993
711 484
471 26
43 879
716 393
613 48
998 866
66 368
465 670
434 777
58 662
810 964
141 202
179 632
669 446
106 412
108 421
623 68
908 301
805 885
691 197
641 477
365 817
79 177
146 394
331 636
357 114
687 345
6...

output:

ok

result:

ok all right

Test #35:

score: 100
Accepted
time: 1ms
memory: 4136kb

input:

1000 2063
152 651
423 569
82 188
469 837
791 178
513 272
388 461
658 688
805 167
400 258
947 616
803 244
645 636
14 715
355 166
504 598
366 78
611 886
284 952
429 434
138 349
423 520
910 760
263 499
282 106
62 525
765 673
425 636
767 432
378 368
406 797
777 46
728 638
337 259
720 551
32 418
893 567
...

output:

mark
3
705 660
822 112
355 335

input:

1000 2066
248 802
794 546
623 693
218 571
171 541
680 852
979 593
675 971
626 425
922 91
636 453
442 4
921 981
257 179
379 396
939 740
878 324
493 892
472 749
715 631
223 215
262 244
916 556
995 956
400 919
61 308
550 26
149 650
914 588
53 796
594 614
23 883
160 917
206 66
126 577
347 973
330 336
44...

output:

ok

result:

ok all right

Test #36:

score: 100
Accepted
time: 1ms
memory: 4108kb

input:

1000 2015
735 560
841 818
908 373
452 621
415 440
682 740
879 685
769 787
78 247
709 376
529 131
838 689
352 699
233 54
420 43
675 580
893 682
570 960
886 186
627 685
824 527
285 801
381 190
545 638
803 864
673 545
675 471
539 857
97 929
72 835
176 54
336 134
674 134
214 557
720 131
480 947
842 993
...

output:

mark
3
783 648
408 22
902 609

input:

1000 2018
934 469
856 292
112 463
9 276
385 391
631 297
792 621
449 281
966 397
826 839
572 126
364 639
569 800
838 541
656 671
791 684
503 372
737 274
826 214
865 523
82 668
737 619
731 427
361 866
989 698
56 306
481 378
952 795
490 100
28 336
755 533
776 595
252 892
451 786
786 238
255 423
541 481...

output:

ok

result:

ok all right

Test #37:

score: 100
Accepted
time: 1ms
memory: 3908kb

input:

1000 2088
740 777
753 465
620 85
563 425
462 640
660 818
506 223
161 680
212 736
832 801
881 351
708 787
743 371
325 128
840 456
832 721
671 768
711 676
967 36
297 541
201 236
348 983
794 78
832 912
840 569
671 857
357 781
263 615
505 283
760 980
279 519
225 480
387 569
407 877
132 284
863 892
600 9...

output:

mark
2
256 52
663 837

input:

1000 2090
215 124
152 914
778 243
890 209
54 631
988 975
461 465
594 421
763 564
358 961
744 810
367 230
580 437
123 377
470 672
139 576
539 394
135 231
607 178
958 565
617 434
588 122
448 735
71 917
777 801
989 360
929 539
291 55
146 706
722 284
486 94
167 615
307 755
275 95
323 470
262 707
688 657...

output:

ok

result:

ok all right

Test #38:

score: 0
Wrong Answer on the first run

input:

1000 2095
820 62
50 81
933 467
775 61
743 331
914 662
41 547
91 695
965 431
215 837
251 67
840 532
289 599
112 235
939 390
316 769
806 938
477 138
916 693
337 373
776 82
795 276
390 706
679 304
951 493
51 821
702 85
6 852
586 638
125 198
298 989
235 203
294 967
785 338
923 718
907 138
534 232
735 70...

output:

ok

input:


output:


result:

wrong answer Token "ok" doesn't correspond to pattern "mark"