QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#604552#8757. 图ucup-team902#AC ✓263ms28860kbC++171.8kb2024-10-02 12:00:532024-10-02 12:00:54

Judging History

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

  • [2024-10-02 12:00:54]
  • 评测
  • 测评结果:AC
  • 用时:263ms
  • 内存:28860kb
  • [2024-10-02 12:00:53]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
int n,m;
map<pair<int,int>,int> mp;
struct E{
    int u,v,c;
    E(int u=0,int v=0,int c=0):u(u),v(v),c(c){}
};
vector<E> e;
struct G{
    vector<E> e;
};
int f[N+5];
int find(int x){ return x==f[x]?x:f[x]=find(f[x]); }
vector<int> e2[N+5];
int fa[N+5],dep[N+5];
void dfs(int u,int tf){
    fa[u]=tf; dep[u]=dep[tf]+1;
    for(auto v:e2[u])
        if(v!=tf) dfs(v,u);
}
void work(G &g,int st,int en){
    for(int i=1;i<=n;i++) e2[i].clear();
    for(auto [u,v,c]:g.e){
        e2[u].push_back(v);
        e2[v].push_back(u);
    }
    dfs(en,0);
    printf("%d ",dep[st]);
    while(st!=en){
        printf("%d ",st);
        st=fa[st];
    }
    printf("%d\n",en);
}
void solve(){
    mp.clear(); e.clear();
    scanf("%d %d",&n,&m);
    // fprintf(stderr,"%d %d\n",n,m);
    for(int i=1,u,v;i<=m;i++){
        scanf("%d %d",&u,&v);
        mp[{u,v}]++;
    }
    for(auto it:mp){
        auto [u,v]=it.first;
        e.push_back({u,v,it.second});
    }
    int k=(m+n-2)/(n-1);
    // printf("%d\n",k);
    int ansu=-1,ansv=-1;
    vector<G> resg;
    while(k--){
        G g;
        for(int i=1;i<=n;i++) f[i]=i;
        for(auto &it:e){
            auto [u,v,c]=it;
            if(c==0) continue;
            if(find(u)!=find(v)){
                if(k==0){
                    ansu=u; ansv=v;
                }
                u=find(u); v=find(v);
                f[u]=v;
                g.e.push_back(it);
                it.c--;
            }
        }
        resg.push_back(g);
    }
    assert(ansu!=-1&&ansv!=-1);
    printf("%d %d\n",ansu,ansv);
    for(auto g:resg)
        work(g,ansu,ansv);
}
int main(){
    int t; scanf("%d",&t);
    while(t--) solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 70ms
memory: 6540kb

input:

10000
2 20
1 2
1 2
2 1
1 2
1 2
2 1
1 2
2 1
1 2
1 2
1 2
1 2
2 1
1 2
1 2
2 1
1 2
1 2
1 2
2 1
2 20
2 1
2 1
2 1
2 1
2 1
1 2
1 2
1 2
1 2
2 1
1 2
1 2
2 1
1 2
1 2
2 1
1 2
1 2
2 1
1 2
2 20
1 2
2 1
1 2
1 2
2 1
2 1
1 2
1 2
2 1
2 1
1 2
1 2
1 2
1 2
2 1
1 2
1 2
1 2
2 1
2 1
2 20
1 2
2 1
2 1
1 2
1 2
1 2
2 1
1 2
2 ...

output:

2 1
2 2 1
2 2 1
2 2 1
2 2 1
2 2 1
2 2 1
2 2 1
2 2 1
2 2 1
2 2 1
2 2 1
2 2 1
2 2 1
2 2 1
2 2 1
2 2 1
2 2 1
2 2 1
2 2 1
2 2 1
2 1
2 2 1
2 2 1
2 2 1
2 2 1
2 2 1
2 2 1
2 2 1
2 2 1
2 2 1
2 2 1
2 2 1
2 2 1
2 2 1
2 2 1
2 2 1
2 2 1
2 2 1
2 2 1
2 2 1
2 2 1
2 1
2 2 1
2 2 1
2 2 1
2 2 1
2 2 1
2 2 1
2 2 1
2 2 1
...

result:

ok Answer correct. (10000 test cases)

Test #2:

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

input:

10000
5 20
2 1
2 5
5 3
3 1
4 5
1 4
4 3
4 5
3 5
5 4
2 3
5 2
3 4
3 5
1 4
4 3
4 2
2 1
1 3
5 1
5 20
4 2
1 3
1 2
4 5
2 4
3 1
5 3
5 1
4 5
4 3
2 4
1 4
4 3
5 2
1 2
3 5
1 5
4 1
3 4
4 3
5 20
1 4
1 3
1 5
5 1
4 5
3 4
4 5
2 3
1 2
2 4
4 5
4 5
2 4
2 5
4 2
4 3
4 2
2 5
2 1
3 1
5 20
2 5
2 3
4 5
4 2
3 4
2 1
5 4
2 5
2 ...

output:

4 5
4 4 1 2 5
5 4 1 2 3 5
3 4 3 5
2 4 5
2 4 5
5 3
3 5 1 3
2 5 3
3 5 4 3
3 5 4 3
2 5 3
4 5
3 4 1 5
3 4 2 5
3 4 2 5
2 4 5
2 4 5
5 2
2 5 2
2 5 2
4 5 3 1 2
3 5 4 2
2 5 2
5 4
3 5 1 4
3 5 1 4
4 5 3 2 4
2 5 4
2 5 4
5 4
3 5 1 4
3 5 1 4
3 5 1 4
3 5 2 4
2 5 4
5 3
4 5 2 1 3
2 5 3
4 5 4 1 3
4 5 2 4 3
2 5 3
5 3
...

result:

ok Answer correct. (10000 test cases)

Test #3:

score: 0
Accepted
time: 51ms
memory: 6796kb

input:

10000
10 20
9 4
8 6
2 10
2 9
7 10
4 6
9 4
2 1
4 7
1 5
7 2
4 1
5 9
7 6
8 2
9 4
5 9
9 8
7 3
2 4
10 20
3 8
8 9
8 7
9 2
3 10
9 3
8 1
9 4
8 9
4 7
7 5
5 10
1 3
3 4
3 7
3 8
3 9
1 4
3 6
2 4
10 20
7 6
8 10
3 8
2 8
4 8
4 8
4 6
4 1
1 7
4 6
5 9
5 2
4 7
10 9
6 7
10 5
2 4
4 1
3 2
4 9
10 20
2 1
9 8
7 6
2 10
9 5
4 ...

output:

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

result:

ok Answer correct. (10000 test cases)

Test #4:

score: 0
Accepted
time: 26ms
memory: 6220kb

input:

2000
50 50
6 10
21 26
12 42
29 2
3 30
3 28
7 44
44 37
11 4
23 12
49 14
34 41
35 48
33 6
27 9
33 1
33 31
43 35
32 31
20 42
27 40
39 29
34 38
21 15
31 17
3 33
17 18
15 44
50 22
20 25
28 44
23 32
3 23
25 30
50 20
17 2
21 41
46 35
26 7
34 45
34 19
21 10
44 4
28 22
36 21
4 49
44 39
4 36
2 15
21 38
50 50
...

output:

50 22
8 50 20 42 12 23 3 28 22
2 50 22
43 47
9 43 36 24 9 46 32 29 15 47
2 43 47
46 25
3 46 38 25
2 46 25
50 12
5 50 42 26 21 12
2 50 12
50 20
6 50 17 19 35 11 20
2 50 20
48 43
9 48 16 6 26 23 3 24 29 43
2 48 43
50 1
6 50 10 8 44 6 1
2 50 1
47 19
7 47 32 30 27 26 15 19
2 47 19
49 1
8 49 39 17 13 6 2...

result:

ok Answer correct. (2000 test cases)

Test #5:

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

input:

200
50 1000
6 33
31 2
17 37
27 22
36 1
35 12
31 3
8 36
22 15
40 45
13 23
23 24
50 46
41 48
49 35
15 30
14 6
7 24
38 27
43 19
30 16
16 31
49 21
47 44
33 9
27 32
48 23
24 33
25 12
23 50
6 27
20 21
48 11
42 23
8 36
3 34
8 14
17 30
27 1
14 40
37 5
23 24
6 24
5 35
38 43
31 48
25 33
4 13
6 37
22 24
31 32
...

output:

50 19
6 50 3 1 2 4 19
5 50 3 4 6 19
6 50 9 7 6 8 19
11 50 13 9 8 5 34 7 6 11 15 19
4 50 17 18 19
7 50 21 11 13 6 17 19
5 50 23 15 27 19
6 50 23 16 15 38 19
9 50 24 21 14 49 18 16 43 19
9 50 26 14 20 16 18 22 43 19
6 50 27 20 14 24 19
9 50 27 22 20 24 17 23 29 19
6 50 29 26 22 31 19
6 50 30 28 27 31 ...

result:

ok Answer correct. (200 test cases)

Test #6:

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

input:

20
100 10000
77 84
14 62
84 5
4 67
99 44
54 18
39 53
58 88
32 3
61 19
76 14
28 72
92 34
20 1
14 66
98 25
53 99
55 40
13 70
42 62
32 41
93 14
74 66
92 62
42 12
94 35
26 65
82 85
100 34
79 47
87 59
4 92
46 4
77 63
17 62
32 23
46 76
61 26
89 41
10 18
17 64
55 61
89 42
8 71
75 89
2 81
9 63
42 32
23 34
7...

output:

100 41
3 100 1 41
6 100 1 3 2 4 41
6 100 1 91 2 4 41
7 100 2 9 3 1 5 41
7 100 4 3 45 2 5 41
4 100 8 5 41
5 100 11 8 6 41
8 100 11 9 4 47 5 6 41
8 100 12 4 8 7 5 6 41
6 100 13 9 6 7 41
6 100 14 10 8 7 41
6 100 15 11 6 7 41
9 100 15 12 9 5 8 27 10 41
11 100 17 4 15 13 7 9 47 8 11 41
9 100 17 4 16 11 3...

result:

ok Answer correct. (20 test cases)

Test #7:

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

input:

100
1000 1999
527 98
626 570
505 814
510 660
334 873
893 329
51 818
256 113
165 543
515 780
905 200
560 363
385 813
82 324
661 719
3 624
175 120
22 480
662 730
701 676
124 107
820 707
288 412
596 842
285 574
209 109
897 789
37 371
399 502
715 361
877 504
68 73
919 671
685 732
866 390
975 122
994 263...

output:

1000 944
19 1000 125 821 330 260 201 154 118 63 69 786 97 266 230 25 924 229 540 944
23 1000 326 449 451 591 94 674 522 204 302 445 232 543 500 316 365 297 727 900 475 929 828 944
2 1000 944
1000 891
9 1000 255 615 66 49 643 43 497 891
16 1000 494 327 219 537 398 636 518 77 422 528 578 536 906 933 8...

result:

ok Answer correct. (100 test cases)

Test #8:

score: 0
Accepted
time: 26ms
memory: 6128kb

input:

1000
100 100
8 93
14 86
43 53
73 87
9 5
30 87
23 88
9 18
89 75
49 53
39 91
58 22
86 27
75 1
57 90
20 40
71 55
58 77
63 46
97 95
6 71
19 92
54 24
50 96
30 50
11 79
70 20
79 24
88 33
8 86
18 60
51 58
66 39
93 31
1 47
41 65
45 12
3 93
62 33
38 49
29 91
3 29
15 51
37 56
54 6
85 95
2 81
36 28
10 98
57 26...

output:

88 33
24 88 23 78 56 96 50 30 87 91 29 3 93 8 86 27 76 53 43 40 20 70 9 62 33
2 88 33
93 13
11 93 45 18 85 59 69 1 23 75 47 13
2 93 13
85 57
9 85 34 15 30 24 69 9 92 57
2 85 57
99 7
23 99 61 63 43 84 78 26 13 98 55 72 15 42 76 21 75 23 88 86 67 87 60 7
2 99 7
86 93
16 86 74 4 71 19 70 13 57 88 5 72 ...

result:

ok Answer correct. (1000 test cases)

Test #9:

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

input:

500
200 399
181 137
41 68
61 54
32 10
41 136
85 112
127 111
51 107
143 189
21 69
149 109
107 120
21 158
175 53
31 48
80 170
46 108
163 85
110 142
2 30
117 128
109 114
142 178
76 43
118 63
36 149
45 74
165 123
43 72
87 185
70 173
132 79
130 163
187 10
189 114
70 22
12 184
200 175
65 169
23 27
1 14
19...

output:

200 175
15 200 79 80 64 26 25 15 10 12 52 29 42 21 158 175
5 200 107 76 78 175
2 200 175
198 156
3 198 17 156
15 198 44 167 107 77 142 127 132 135 89 109 118 76 39 156
2 198 156
199 139
21 199 97 49 17 45 58 28 7 178 25 26 93 27 33 161 47 55 73 62 35 139
17 199 123 165 190 126 117 152 57 77 98 108 4...

result:

ok Answer correct. (500 test cases)

Test #10:

score: 0
Accepted
time: 56ms
memory: 6388kb

input:

2197
10 91
7 3
7 9
9 2
1 10
7 1
6 8
4 8
2 10
7 6
5 3
4 10
9 3
1 4
2 9
5 4
5 6
3 7
6 1
1 9
2 6
3 4
6 9
8 7
6 7
7 4
8 7
9 3
10 7
10 6
2 5
2 7
8 10
10 1
7 4
10 4
9 2
7 6
3 10
6 4
1 8
8 9
6 7
10 9
3 2
2 5
10 5
4 7
5 3
9 4
1 5
1 4
8 4
4 10
7 3
6 7
4 2
3 4
9 2
1 10
6 1
8 3
2 9
9 10
9 5
3 4
5 8
9 3
7 1
6 1...

output:

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

result:

ok Answer correct. (2197 test cases)

Test #11:

score: 0
Accepted
time: 45ms
memory: 6348kb

input:

1980
5 101
3 5
4 2
5 1
1 4
2 5
1 3
2 5
3 2
4 2
3 1
1 2
5 3
3 4
3 1
1 3
5 3
1 4
2 4
2 3
4 2
4 5
4 5
1 2
3 1
3 4
1 2
3 5
4 1
2 4
3 5
4 3
4 1
2 1
2 1
5 4
5 3
3 5
2 5
4 1
5 3
2 3
3 4
3 4
5 2
3 2
4 3
2 3
4 3
1 5
2 1
1 3
1 4
1 4
2 5
2 1
1 3
3 5
5 3
1 5
3 4
4 2
3 5
4 2
2 4
4 1
3 5
3 5
5 4
1 4
5 3
5 1
5 3
1...

output:

5 4
3 5 1 4
3 5 1 4
3 5 1 4
4 5 2 1 4
4 5 2 1 4
4 5 2 1 4
4 5 2 1 4
3 5 2 4
4 5 3 2 4
4 5 3 2 4
4 5 3 2 4
4 5 3 2 4
4 5 3 2 4
3 5 3 4
3 5 3 4
3 5 3 4
3 5 3 4
3 5 3 4
2 5 4
2 5 4
3 5 2 4
3 5 3 4
3 5 3 4
3 5 3 4
2 5 4
2 5 4
5 4
3 5 1 4
3 5 1 4
3 5 1 4
3 5 1 4
4 5 2 1 4
4 5 2 1 4
4 5 2 1 4
4 5 2 1 4
4 ...

result:

ok Answer correct. (1980 test cases)

Test #12:

score: 0
Accepted
time: 263ms
memory: 28860kb

input:

1
100000 200000
34863 14128
21925 31963
32836 60679
64214 73508
66150 45252
9601 33518
33904 58681
94179 37263
91962 58845
44150 57595
75389 55087
95549 80645
35339 82663
93639 89411
91288 79966
6158 91046
34153 16675
38098 20451
49822 20670
34821 40807
67167 98424
75186 55129
47388 80048
47576 3327...

output:

100000 17962
89 100000 29524 2662 7231 20657 77837 19471 18586 12979 52068 4088 67554 9964 69147 7900 7087 1163 7884 6687 13700 49279 12741 17797 14690 1575 16185 16150 10419 1327 84588 15429 33738 3565 64009 2801 8950 16563 78812 14891 60180 14580 24176 3290 7302 5136 4953 18610 10790 18570 18078 1...

result:

ok Answer correct. (1 test case)

Test #13:

score: 0
Accepted
time: 125ms
memory: 19740kb

input:

1
100000 100000
83552 10530
25783 47244
84923 13681
21334 91194
91778 58467
19661 74982
25591 89762
59524 51208
87846 82043
11266 66764
81526 43233
68225 71631
59267 57074
14783 69153
4005 38103
10428 8712
16106 97817
65055 2008
87601 98588
44816 64853
13936 1829
49508 54999
20100 23207
3098 59651
5...

output:

98907 96341
345 98907 19941 1511 56667 77176 82337 16529 83480 44608 4823 7751 58866 91423 15134 65176 64404 20516 4917 15894 89167 41765 76221 92789 756 35353 47131 34578 9146 66780 92632 57738 86878 82414 69729 83486 73214 16212 21415 94326 31549 90966 1503 40634 579 83423 88258 80347 29178 47777 ...

result:

ok Answer correct. (1 test case)

Test #14:

score: 0
Accepted
time: 36ms
memory: 7888kb

input:

10
10000 10000
3288 319
1296 6368
8450 2814
7356 5128
7375 44
5324 3611
9164 7555
1308 5753
1325 8813
5264 796
602 9263
6701 6141
3612 4277
611 5775
8960 5850
4706 9495
7751 9401
8316 7060
8524 8033
7342 4672
2503 3504
4515 4649
3881 1881
2962 4138
9655 9539
9043 4098
2631 6216
1198 9724
6105 2802
6...

output:

9959 5172
232 9959 3821 7355 2843 4532 4927 209 850 9137 4445 3293 5292 7483 2493 2463 8430 5429 1508 6277 9529 1154 4068 9835 1804 4752 9330 1353 6059 6715 5494 8455 8601 4635 4409 5548 5900 2599 1697 1445 7373 9341 311 2510 8006 3021 1625 1773 2760 6285 4906 3942 8082 4398 1801 8195 2225 5012 6728...

result:

ok Answer correct. (10 test cases)

Test #15:

score: 0
Accepted
time: 22ms
memory: 6140kb

input:

1000
100 100
8 93
14 86
43 53
73 87
9 5
30 87
23 88
9 18
89 75
49 53
39 91
58 22
86 27
75 1
57 90
20 40
71 55
58 77
63 46
97 95
6 71
19 92
54 24
50 96
30 50
11 79
70 20
79 24
88 33
8 86
18 60
51 58
66 39
93 31
1 47
41 65
45 12
3 93
62 33
38 49
29 91
3 29
15 51
37 56
54 6
85 95
2 81
36 28
10 98
57 26...

output:

88 33
24 88 23 78 56 96 50 30 87 91 29 3 93 8 86 27 76 53 43 40 20 70 9 62 33
2 88 33
93 13
11 93 45 18 85 59 69 1 23 75 47 13
2 93 13
85 57
9 85 34 15 30 24 69 9 92 57
2 85 57
99 7
23 99 61 63 43 84 78 26 13 98 55 72 15 42 76 21 75 23 88 86 67 87 60 7
2 99 7
86 93
16 86 74 4 71 19 70 13 57 88 5 72 ...

result:

ok Answer correct. (1000 test cases)

Test #16:

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

input:

500
200 399
11 16
126 2
70 102
89 163
54 149
84 74
200 175
126 2
98 56
140 188
5 87
107 120
68 133
19 71
135 116
11 78
105 193
63 44
129 33
182 123
83 161
125 6
86 171
44 2
12 184
130 66
78 175
182 141
188 40
154 42
86 60
106 192
90 189
142 135
12 73
95 146
88 62
161 114
101 42
19 106
154 42
122 137...

output:

182 141
10 182 44 2 126 176 48 98 125 78 141
2 182 141
2 182 141
195 124
47 195 39 119 200 29 55 114 17 14 111 31 127 92 25 194 181 121 169 126 140 81 180 23 145 125 85 142 160 163 106 24 45 159 177 89 97 135 98 129 38 61 51 60 21 105 101 124
2 195 124
2 195 124
190 175
30 190 20 12 127 18 135 142 3...

result:

ok Answer correct. (500 test cases)

Test #17:

score: 0
Accepted
time: 38ms
memory: 6760kb

input:

2197
10 91
5 8
7 6
5 10
10 5
8 5
7 6
6 7
6 7
9 2
2 6
2 6
8 5
3 5
10 5
10 5
2 9
6 7
5 2
2 5
2 9
3 4
3 5
2 6
5 10
2 5
3 4
1 6
7 6
10 5
6 1
2 9
4 3
5 8
1 6
2 6
2 5
3 9
1 6
5 3
1 6
5 2
6 1
2 9
3 4
6 1
4 3
2 9
2 9
3 5
8 5
3 5
10 5
6 2
7 6
5 2
8 5
2 6
2 6
5 8
5 3
2 5
9 2
1 6
2 6
5 10
2 6
4 3
7 6
3 5
10 5
...

output:

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

result:

ok Answer correct. (2197 test cases)

Test #18:

score: 0
Accepted
time: 39ms
memory: 6404kb

input:

1980
5 101
4 1
1 2
3 1
1 4
2 1
1 2
3 5
3 1
2 1
3 1
3 1
1 4
2 1
2 1
2 1
1 2
5 3
1 2
2 1
3 1
3 1
4 1
4 1
1 2
3 1
3 1
2 1
3 5
2 1
1 4
2 1
1 3
4 1
1 3
3 5
1 2
3 5
1 4
1 2
1 3
4 1
1 4
3 5
1 4
1 3
4 1
1 2
1 3
5 3
5 3
1 4
1 2
3 1
4 1
4 1
3 5
1 2
4 1
1 2
1 3
1 2
3 5
5 3
1 2
1 3
1 3
4 1
4 1
5 3
3 5
4 1
3 5
5...

output:

4 1
2 4 1
2 4 1
2 4 1
2 4 1
2 4 1
2 4 1
2 4 1
2 4 1
2 4 1
2 4 1
3 4 3 1
2 4 1
2 4 1
2 4 1
2 4 1
2 4 1
2 4 1
2 4 1
2 4 1
2 4 1
2 4 1
2 4 1
2 4 1
2 4 1
2 4 1
2 4 1
4 2
2 4 2
2 4 2
2 4 2
2 4 2
2 4 2
2 4 2
2 4 2
2 4 2
2 4 2
2 4 2
2 4 2
2 4 2
2 4 2
3 4 1 2
2 4 2
2 4 2
2 4 2
2 4 2
2 4 2
2 4 2
2 4 2
2 4 2
...

result:

ok Answer correct. (1980 test cases)

Test #19:

score: 0
Accepted
time: 253ms
memory: 24840kb

input:

1
100000 200000
87045 64020
81145 29667
96830 91785
89750 28062
45195 59300
91075 91364
78904 20649
70802 2933
94952 13184
34881 9027
6909 45228
72094 87157
12710 6185
79492 76809
82773 25162
70583 95131
80195 23414
66965 46121
39034 27901
66559 13084
92952 38920
10715 65225
63505 2126
94217 79830
9...

output:

98587 37187
138 98587 90538 72153 29713 30197 66104 75148 1469 5583 2778 41754 5745 39941 21893 47962 70092 68838 26465 72340 18431 97559 9804 3864 65036 72819 18264 4476 80432 65867 26524 69599 90143 93966 44701 25263 14953 28421 9139 43887 19153 31885 24621 40276 73551 10997 52910 59943 6334 93462...

result:

ok Answer correct. (1 test case)

Test #20:

score: 0
Accepted
time: 103ms
memory: 19612kb

input:

1
100000 100000
83552 10530
25783 47244
84923 13681
21334 91194
91778 58467
19661 74982
25591 89762
59524 51208
87846 82043
11266 66764
81526 43233
68225 71631
59267 57074
14783 69153
4005 38103
10428 8712
16106 97817
65055 2008
87601 98588
44816 64853
13936 1829
49508 54999
20100 23207
3098 59651
5...

output:

98907 96341
345 98907 19941 1511 56667 77176 82337 16529 83480 44608 4823 7751 58866 91423 15134 65176 64404 20516 4917 15894 89167 41765 76221 92789 756 35353 47131 34578 9146 66780 92632 57738 86878 82414 69729 83486 73214 16212 21415 94326 31549 90966 1503 40634 579 83423 88258 80347 29178 47777 ...

result:

ok Answer correct. (1 test case)

Test #21:

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

input:

10
10000 10000
3288 319
1296 6368
8450 2814
7356 5128
7375 44
5324 3611
9164 7555
1308 5753
1325 8813
5264 796
602 9263
6701 6141
3612 4277
611 5775
8960 5850
4706 9495
7751 9401
8316 7060
8524 8033
7342 4672
2503 3504
4515 4649
3881 1881
2962 4138
9655 9539
9043 4098
2631 6216
1198 9724
6105 2802
6...

output:

9959 5172
232 9959 3821 7355 2843 4532 4927 209 850 9137 4445 3293 5292 7483 2493 2463 8430 5429 1508 6277 9529 1154 4068 9835 1804 4752 9330 1353 6059 6715 5494 8455 8601 4635 4409 5548 5900 2599 1697 1445 7373 9341 311 2510 8006 3021 1625 1773 2760 6285 4906 3942 8082 4398 1801 8195 2225 5012 6728...

result:

ok Answer correct. (10 test cases)

Test #22:

score: 0
Accepted
time: 43ms
memory: 6880kb

input:

20
1000 9991
608 923
654 599
933 66
70 763
831 458
568 444
779 393
190 673
732 818
283 551
630 583
95 237
278 681
343 514
190 613
96 150
408 366
995 927
361 632
97 217
460 112
838 136
975 614
897 726
181 42
164 323
243 512
188 849
530 636
822 817
259 623
182 776
442 562
911 462
392 313
143 234
669 1...

output:

982 730
37 982 19 390 393 677 828 100 263 156 69 588 65 321 845 565 657 973 371 458 692 760 97 172 548 153 298 953 342 498 384 508 62 51 511 859 290 730
2 982 730
2 982 730
2 982 730
2 982 730
2 982 730
2 982 730
2 982 730
2 982 730
2 982 730
2 982 730
908 780
53 908 14 283 989 199 94 171 174 921 76...

result:

ok Answer correct. (20 test cases)

Test #23:

score: 0
Accepted
time: 59ms
memory: 7024kb

input:

422
3 733
3 1
2 1
1 2
1 3
3 1
3 1
2 3
2 3
1 3
1 3
2 1
2 3
2 3
3 1
3 1
2 3
3 2
2 1
1 3
2 3
2 1
2 1
3 1
2 3
2 1
2 3
2 3
2 3
2 3
3 1
2 1
2 3
1 2
2 1
2 1
3 2
3 1
3 1
1 2
3 2
2 3
1 3
2 1
2 3
1 3
1 2
3 1
3 1
2 3
1 2
1 3
1 2
2 1
3 1
1 3
3 1
3 1
3 2
1 3
3 1
3 1
3 1
3 1
2 1
2 1
1 2
1 3
3 1
1 3
3 1
1 3
3 2
1 ...

output:

3 1
2 3 1
2 3 1
2 3 1
2 3 1
2 3 1
2 3 1
2 3 1
2 3 1
2 3 1
2 3 1
2 3 1
2 3 1
2 3 1
2 3 1
2 3 1
2 3 1
2 3 1
2 3 1
2 3 1
2 3 1
2 3 1
2 3 1
2 3 1
2 3 1
2 3 1
2 3 1
2 3 1
2 3 1
2 3 1
2 3 1
2 3 1
2 3 1
2 3 1
2 3 1
2 3 1
2 3 1
2 3 1
2 3 1
2 3 1
2 3 1
2 3 1
2 3 1
2 3 1
2 3 1
2 3 1
2 3 1
2 3 1
2 3 1
2 3 1
2 ...

result:

ok Answer correct. (422 test cases)

Test #24:

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

input:

46
6 3725
3 4
6 4
3 5
6 5
4 6
6 5
2 6
2 6
5 4
4 3
1 6
3 5
6 4
6 3
3 4
2 3
1 6
2 6
5 2
4 3
5 2
6 2
2 6
6 1
1 6
3 5
3 4
3 1
5 4
1 3
1 4
6 2
1 2
5 3
3 6
6 5
4 6
1 6
4 1
4 6
1 5
1 2
6 5
3 4
4 6
1 4
2 4
4 5
3 5
6 4
4 6
1 2
3 2
4 6
2 4
3 2
6 3
4 2
3 4
2 3
4 5
6 5
6 4
3 5
4 1
1 3
2 3
1 3
5 3
5 1
5 1
5 1
5 ...

output:

6 5
3 6 1 5
3 6 1 5
3 6 1 5
3 6 1 5
3 6 1 5
3 6 1 5
3 6 1 5
3 6 1 5
3 6 1 5
3 6 1 5
3 6 1 5
3 6 1 5
3 6 1 5
3 6 1 5
3 6 1 5
3 6 1 5
3 6 1 5
3 6 1 5
3 6 1 5
3 6 1 5
3 6 1 5
3 6 1 5
3 6 1 5
3 6 1 5
3 6 1 5
3 6 1 5
3 6 1 5
3 6 1 5
3 6 1 5
3 6 1 5
3 6 1 5
3 6 1 5
3 6 1 5
3 6 1 5
3 6 1 5
3 6 1 5
3 6 1 5
...

result:

ok Answer correct. (46 test cases)

Test #25:

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

input:

199
788 1339
53 304
46 671
763 311
642 211
746 529
591 661
87 400
252 103
311 359
111 320
437 445
435 406
351 666
202 564
781 713
203 151
576 587
197 458
280 577
26 256
118 9
664 554
111 359
112 267
151 36
578 740
631 166
26 80
200 327
55 289
570 342
202 243
714 322
751 763
288 123
340 752
73 426
26...

output:

786 403
21 786 284 163 605 124 25 722 45 16 94 91 742 103 69 148 86 756 77 276 294 403
2 786 403
883 709
47 883 650 467 41 163 200 312 39 80 830 69 623 36 84 33 671 136 101 65 634 157 117 646 159 175 575 179 160 77 300 121 30 141 518 55 161 188 311 88 196 492 78 204 349 588 643 709
3 883 283 709
2 8...

result:

ok Answer correct. (199 test cases)

Test #26:

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

input:

1
100 200000
31 47
24 16
52 62
47 68
75 53
24 73
31 98
23 30
19 87
3 53
26 87
64 93
32 98
39 94
90 56
90 89
15 17
62 57
9 83
35 56
20 88
19 10
59 32
75 22
69 59
97 5
38 71
24 50
47 48
31 47
1 30
14 76
46 4
23 46
3 19
27 74
49 31
11 17
32 53
43 71
7 87
42 72
90 20
100 8
98 64
23 72
60 20
10 27
78 93
...

output:

100 80
3 100 1 80
3 100 1 80
3 100 1 80
3 100 1 80
3 100 1 80
3 100 1 80
3 100 1 80
3 100 1 80
3 100 1 80
3 100 1 80
3 100 1 80
3 100 1 80
3 100 1 80
3 100 1 80
3 100 1 80
3 100 1 80
3 100 1 80
4 100 1 2 80
4 100 1 2 80
4 100 1 2 80
4 100 1 2 80
4 100 1 2 80
4 100 1 2 80
4 100 1 2 80
4 100 1 2 80
4 ...

result:

ok Answer correct. (1 test case)

Test #27:

score: 0
Accepted
time: 32ms
memory: 8600kb

input:

1
11 199991
2 10
4 1
2 5
6 1
9 11
5 2
1 10
10 4
5 7
1 4
4 8
7 3
6 3
7 2
1 7
7 6
6 3
10 6
9 10
7 4
1 4
5 4
2 1
3 11
4 11
9 3
7 6
9 2
7 9
4 6
5 7
10 1
3 1
7 2
11 9
11 2
9 8
1 8
5 11
3 2
6 5
10 11
11 3
4 7
4 1
5 3
7 6
8 9
3 5
7 8
3 2
7 5
10 9
8 2
10 6
9 11
10 4
11 7
10 3
11 1
6 2
1 5
9 2
11 1
4 8
8 7
6...

output:

11 10
3 11 1 10
3 11 1 10
3 11 1 10
3 11 1 10
3 11 1 10
3 11 1 10
3 11 1 10
3 11 1 10
3 11 1 10
3 11 1 10
3 11 1 10
3 11 1 10
3 11 1 10
3 11 1 10
3 11 1 10
3 11 1 10
3 11 1 10
3 11 1 10
3 11 1 10
3 11 1 10
3 11 1 10
3 11 1 10
3 11 1 10
3 11 1 10
3 11 1 10
3 11 1 10
3 11 1 10
3 11 1 10
3 11 1 10
3 11...

result:

ok Answer correct. (1 test case)

Test #28:

score: 0
Accepted
time: 22ms
memory: 8724kb

input:

1
11 199991
1 11
3 8
3 8
7 3
9 11
3 8
2 3
1 11
3 7
7 4
7 3
8 3
9 11
11 1
9 8
10 8
3 2
11 9
1 11
9 8
4 6
3 2
3 7
7 3
11 9
11 1
3 7
6 4
7 5
2 3
6 4
4 6
8 3
5 7
3 7
5 7
5 7
3 8
5 7
11 9
4 7
9 8
10 8
1 11
4 6
9 8
8 9
2 3
7 4
6 4
2 3
7 4
11 9
3 2
8 9
11 1
9 8
2 3
3 8
7 4
7 4
8 9
4 7
11 1
8 10
3 8
10 8
6 ...

output:

11 9
2 11 9
2 11 9
2 11 9
2 11 9
2 11 9
2 11 9
2 11 9
2 11 9
2 11 9
2 11 9
2 11 9
2 11 9
2 11 9
2 11 9
2 11 9
2 11 9
2 11 9
2 11 9
2 11 9
2 11 9
2 11 9
2 11 9
2 11 9
2 11 9
2 11 9
2 11 9
2 11 9
2 11 9
2 11 9
2 11 9
2 11 9
2 11 9
2 11 9
2 11 9
2 11 9
2 11 9
2 11 9
2 11 9
2 11 9
2 11 9
2 11 9
2 11 9
2...

result:

ok Answer correct. (1 test case)

Test #29:

score: 0
Accepted
time: 26ms
memory: 8580kb

input:

1
101 199901
88 63
18 41
58 27
11 39
70 51
24 81
48 98
54 83
16 59
32 91
94 46
64 45
16 80
26 97
93 35
66 42
21 42
2 50
86 55
4 68
85 50
50 42
57 66
37 8
1 85
70 51
18 16
52 16
56 96
24 81
66 90
32 91
77 34
55 86
83 44
42 66
67 1
23 100
56 96
10 73
1 85
68 85
75 23
39 76
41 18
17 1
41 47
80 83
16 80...

output:

83 80
21 83 54 10 79 28 48 98 64 45 91 32 4 68 85 50 42 66 76 52 16 80
2 83 80
2 83 80
2 83 80
2 83 80
2 83 80
2 83 80
2 83 80
2 83 80
2 83 80
2 83 80
2 83 80
2 83 80
2 83 80
2 83 80
2 83 80
2 83 80
2 83 80
2 83 80
2 83 80
2 83 80
2 83 80
2 83 80
2 83 80
2 83 80
2 83 80
2 83 80
2 83 80
2 83 80
2 83 ...

result:

ok Answer correct. (1 test case)

Test #30:

score: 0
Accepted
time: 61ms
memory: 8136kb

input:

16
147 29384
50 25
83 135
61 141
33 65
33 70
64 130
39 43
5 142
64 58
45 68
55 115
34 110
75 42
136 71
89 53
65 126
125 44
40 135
29 15
6 120
111 107
132 147
86 125
28 76
41 79
33 94
19 65
45 99
16 69
133 106
136 71
83 34
93 70
77 22
62 72
51 27
111 70
125 102
39 99
113 84
102 61
53 8
81 83
63 105
3...

output:

147 103
4 147 1 2 103
4 147 1 2 103
3 147 2 103
5 147 2 4 5 103
6 147 2 4 5 6 103
6 147 2 3 1 6 103
4 147 3 7 103
5 147 3 6 8 103
7 147 4 20 5 7 11 103
9 147 4 44 3 6 13 8 11 103
7 147 4 6 3 9 11 103
7 147 5 6 3 9 11 103
9 147 6 74 4 9 11 1 12 103
10 147 6 27 7 5 9 11 2 12 103
7 147 7 5 9 4 12 103
1...

result:

ok Answer correct. (16 test cases)