QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#163684#5545. Contingency Planideograph_advantageWA 69ms15908kbC++173.9kb2023-09-04 14:00:292023-09-04 14:00:29

Judging History

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

  • [2023-09-04 14:00:29]
  • 评测
  • 测评结果:WA
  • 用时:69ms
  • 内存:15908kb
  • [2023-09-04 14:00:29]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define iter(v) v.begin(), v.end()
#define SZ(v) (int)v.size()
#define pb emplace_back
#define ff first
#define ss second

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

#ifdef zisk
void debug(){ cerr << "\n"; }
template<class T, class ... U>
void debug(T a, U ... b){ cerr << a << " ", debug(b...); }
template<class T> void pary(T l, T r){
    while(l != r) cerr << *l << " ", l++;
    cerr << "\n";
}
#else
#define debug(...) void()
#define pary(...) void()
#endif

template<class A, class B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.ff << ',' << p.ss << ')';
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    vector<vector<int>> g(n + 1);
    vector<int> deg(n + 1);
    vector<pii> e(n - 1);
    for (int i = 0;i < n - 1;i++) {
        int u, v;
        cin >> u >> v;
        e[i] = pii(u, v);
        g[u].push_back(v);
        g[v].push_back(u);
        deg[u]++;
        deg[v]++;
    }

    int rt = -1;
    for(int i = 1; i <= n; i++){
        if(deg[i] == n - 1){
            cout << "-1\n";
            return 0;
        }
        if(deg[i] > 1) rt = i;
    }

    vector<int> dpt(n + 1), par(n + 1), root(n + 1);
    vector<bool> del(n + 1);
    function<void(int, int, int, int)> dfs = [&](int now, int p, int no, int r){
        par[now] = p;
        root[now] = r;
        for(int i : g[now]){
            if(del[i] || i == p || i == no) continue;
            dpt[i] = dpt[now] + 1;
            dfs(i, now, no, r);
        }
    };

    dfs(rt, rt, -1, rt);

    vector<pii> ans;
    bool leaf = true;
    int A = -1, B = -1;
    set<int> qq;
    for(int i : g[rt]) qq.insert(i);
    for(auto [u, v] : e){
        debug("solve", u, v);
        if(!leaf){
            if(dpt[u] < dpt[v]) swap(u, v);
            debug("del", u, v, dpt[u], dpt[v]);
            if(root[u] == A) ans.pb(pii(u, B)), debug(u, B);
            else ans.pb(pii(u, A)), debug(u, A);
            continue;
        }
        
        if(deg[u] > 1 && deg[v] > 1){
            bool ok = false;
            for(int i : g[u]){
                if(i == v || del[i]) continue;
                for(int j : g[v]){
                    if(j == u || del[j]) continue;
                    debug("owo", i, j);
                    ans.pb(pii(i, j));
                    ok = true;
                    dpt[i] = dpt[j] = 0;
                    dfs(i, i, v, i);
                    dfs(j, j, u, j);
                    pary(iter(dpt));
                    pary(iter(root));
                    leaf = false;
                    A = i; B = j;
                    break;
                }
                if(ok) break;
            }
            continue;
        }

        if(deg[u] == 1 && deg[v] == 1 && u == rt) swap(u, v);
        else if(deg[v] == 1) swap(u, v);
        del[u] = true;
        deg[v]--;

        if(par[u] != rt){
            ans.pb(pii(u, rt));
            continue;
        }
        qq.erase(u);
        if(!qq.empty()){
            ans.pb(pii(u, *qq.begin()));
            continue;
        }
        
        bool ok = false;
        int c = -1;
        for(int i = 1; i <= n; i++){
            if(par[i] == u) c = i;
            if(i != rt && i != u && par[i] != u && par[i] != rt){
                ans.pb(pii(u, i));
                ok = true;
                break;
            }
        }
        if(!ok){
            assert(c != -1);
            for(int i = 1; i <= n; i++){
                if(par[i] == rt && i != u){
                    ans.pb(pii(i, c));
                    ok = true;
                    break;
                }
            }
        }
        assert(ok);

    }

    for(auto [u, v] : ans) cout << u << " " << v << "\n";
    
}

詳細信息

Test #1:

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

input:

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

output:

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

result:

ok AC

Test #2:

score: 0
Accepted
time: 1ms
memory: 3620kb

input:

3
1 2
2 3

output:

-1

result:

ok AC

Test #3:

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

input:

2
2 1

output:

-1

result:

ok AC

Test #4:

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

input:

5
2 1
2 3
2 4
4 5

output:

1 4
3 4
2 5
5 1

result:

ok AC

Test #5:

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

input:

5
1 4
3 4
4 5
2 5

output:

1 5
3 5
4 2
5 2

result:

ok AC

Test #6:

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

input:

5
5 2
1 2
4 2
3 4

output:

5 4
1 4
2 3
4 3

result:

ok AC

Test #7:

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

input:

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

output:

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

result:

ok AC

Test #8:

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

input:

20000
7662 1
9205 1
5971 1
1 9886
1 18853
14108 1
998 1
1 14958
7100 1
1 2670
1 18493
13838 1
4644 1
2139 1
1 18540
1 14081
1 16836
1 9357
245 1
242 1
1 13472
1 1471
3792 1
1 17875
13976 1
1 15085
1 17283
15014 1
17477 1
11578 1
18441 1
1 14367
3018 1
1 7186
1 4939
2470 1
2993 1
6175 1
1 19886
1 125...

output:

7662 11055
9205 11055
5971 11055
9886 11055
18853 11055
14108 11055
998 11055
14958 11055
7100 11055
2670 11055
18493 11055
13838 11055
4644 11055
2139 11055
18540 11055
14081 11055
16836 11055
9357 11055
245 11055
242 11055
13472 11055
1471 11055
3792 11055
17875 11055
13976 11055
15085 11055
17283...

result:

ok AC

Test #9:

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

input:

20000
8854 1
15635 1
8088 1
1 12138
12367 1
1 15051
6392 1
15564 1
17334 1
1 10164
8704 1
1 13795
1 10292
12108 1
1 50
4 1
1 18364
13341 1
19203 1
1 3017
1 5133
3499 1
19202 1
1 10304
12975 1
1 17220
1 1716
1 4158
1 16763
1 301
1 16645
8690 1
1 10064
16977 1
1 19618
1 5471
1 8763
3997 1
1 3283
11332...

output:

8854 17288
15635 17288
8088 17288
12138 17288
12367 17288
15051 17288
6392 17288
15564 17288
17334 17288
10164 17288
8704 17288
13795 17288
10292 17288
12108 17288
50 17288
4 17288
18364 17288
13341 17288
19203 17288
3017 17288
5133 17288
3499 17288
19202 17288
10304 17288
12975 17288
17220 17288
17...

result:

ok AC

Test #10:

score: 0
Accepted
time: 1ms
memory: 5124kb

input:

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

output:

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

result:

ok AC

Test #11:

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

input:

20000
1 13291
13291 19998
3314 13291
13291 3339
13291 10237
13244 13291
13291 3392
13291 4459
13291 17335
13291 10356
6124 13291
13291 4470
12896 13291
13291 12094
3309 13291
13319 13291
13291 15658
13291 2305
13291 13710
13291 16520
13291 16234
6697 13291
13291 6686
9187 13291
13291 43
13291 2764
1...

output:

1 2
19998 2
3314 2
3339 2
10237 2
13244 2
3392 2
4459 2
17335 2
10356 2
6124 2
4470 2
12896 2
12094 2
3309 2
13319 2
15658 2
2305 2
13710 2
16520 2
16234 2
6697 2
6686 2
9187 2
43 2
2764 2
9061 2
8113 2
8449 2
3304 2
16249 2
3859 2
5651 2
8941 2
13460 2
19932 2
10868 2
10878 2
12114 2
2249 2
8469 2
...

result:

ok AC

Test #12:

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

input:

20000
4030 5565
1206 5565
5565 8947
4887 5565
14605 5565
5565 2947
5565 9038
5565 5326
5565 9021
11087 5565
5565 19562
895 5565
14653 5565
5565 10803
5565 9750
5565 16331
4689 5565
14307 5565
11631 5565
5565 13244
10554 5565
8112 5565
5565 9394
5565 5945
15279 5565
5565 15512
1334 5565
5565 6025
556...

output:

4030 14227
1206 14227
8947 14227
4887 14227
14605 14227
2947 14227
9038 14227
5326 14227
9021 14227
11087 14227
19562 14227
895 14227
14653 14227
10803 14227
9750 14227
16331 14227
4689 14227
14307 14227
11631 14227
13244 14227
10554 14227
8112 14227
9394 14227
5945 14227
15279 14227
15512 14227
133...

result:

ok AC

Test #13:

score: 0
Accepted
time: 24ms
memory: 12364kb

input:

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

output:

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

result:

ok AC

Test #14:

score: 0
Accepted
time: 1ms
memory: 3560kb

input:

5
2 1
3 2
4 3
5 4

output:

1 4
2 4
3 5
4 5

result:

ok AC

Test #15:

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

input:

100000
21871 1
13678 1
27196 1
70437 1
1 35891
1 43010
28018 1
1 64489
61157 1
1 35572
1 41613
1 73049
93865 1
83507 1
1 92127
86278 1
1 15004
1 44154
2005 1
1 94210
41410 1
1 5886
69836 1
1 24120
1 80802
1 9940
66220 1
66549 1
1 20103
1 5
1 33021
35482 1
76185 1
34850 1
1 55173
1 72488
1 76286
1 99...

output:

21871 63055
13678 63055
27196 63055
70437 63055
35891 63055
43010 63055
28018 63055
64489 63055
61157 63055
35572 63055
41613 63055
73049 63055
93865 63055
83507 63055
92127 63055
86278 63055
15004 63055
44154 63055
2005 63055
94210 63055
41410 63055
5886 63055
69836 63055
24120 63055
80802 63055
99...

result:

ok AC

Test #16:

score: 0
Accepted
time: 29ms
memory: 12444kb

input:

100000
1 12976
28108 1
87682 1
79359 1
16128 1
1 90652
1 55874
27276 1
1 66899
1 10296
1 37870
1 78978
26221 1
28589 1
1 46430
32252 1
22407 1
68230 1
64944 1
1 53457
31023 1
1 57101
1 82578
1 33273
69683 1
64357 1
1 32517
1 45623
1 29497
41082 1
1 43731
1 28620
1 64304
1 23462
1 81982
1 91877
1 309...

output:

12976 49349
28108 49349
87682 49349
79359 49349
16128 49349
90652 49349
55874 49349
27276 49349
66899 49349
10296 49349
37870 49349
78978 49349
26221 49349
28589 49349
46430 49349
32252 49349
22407 49349
68230 49349
64944 49349
53457 49349
31023 49349
57101 49349
82578 49349
33273 49349
69683 49349
...

result:

ok AC

Test #17:

score: 0
Accepted
time: 28ms
memory: 12352kb

input:

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

output:

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

result:

ok AC

Test #18:

score: 0
Accepted
time: 29ms
memory: 12372kb

input:

100000
15924 1
13919 15924
86413 15924
15924 78418
36904 15924
15924 60478
15924 78563
15924 23855
63531 15924
15574 15924
73713 15924
62532 15924
15924 19461
15924 80750
15924 57012
15924 27046
55780 15924
69619 15924
58970 15924
65824 15924
15924 3195
26782 15924
71411 15924
84915 15924
95347 1592...

output:

1 21982
13919 21982
86413 21982
78418 21982
36904 21982
60478 21982
78563 21982
23855 21982
63531 21982
15574 21982
73713 21982
62532 21982
19461 21982
80750 21982
57012 21982
27046 21982
55780 21982
69619 21982
58970 21982
65824 21982
3195 21982
26782 21982
71411 21982
84915 21982
95347 21982
53739...

result:

ok AC

Test #19:

score: 0
Accepted
time: 69ms
memory: 15908kb

input:

100000
40659 47250
51514 40659
40659 83613
16333 40659
25291 40659
40659 61711
40659 37621
40659 66805
40659 59550
67744 40659
40659 46644
40659 21771
40659 98164
40659 6655
75053 40659
90431 40659
40659 58023
48769 40659
11506 40659
19125 40659
52852 40659
98702 40659
53360 40659
40659 3999
66767 4...

output:

47250 1
51514 1
83613 1
16333 1
25291 1
61711 1
37621 1
66805 1
59550 1
67744 1
46644 1
21771 1
98164 1
6655 1
75053 1
90431 1
58023 1
48769 1
11506 1
19125 1
52852 1
98702 1
53360 1
3999 1
66767 1
82867 1
10045 1
17184 1
77910 1
18776 1
86383 1
20673 1
68349 1
65580 1
45242 1
52336 1
96304 1
90409 ...

result:

ok AC

Test #20:

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

input:

20000
13211 1
1 10767
13211 16998
13211 495
10767 7635
10767 6994
10669 16998
1369 16998
495 4745
722 495
7635 251
3552 7635
7267 6994
6994 1772
10669 18929
10669 9328
3076 1369
1369 14212
4745 284
4745 9599
722 6137
722 10565
15137 251
5349 251
16431 3552
3552 15719
7267 10917
598 7267
19533 1772
1...

output:

16998 10767
1 16998
13211 10767
495 10767
7635 16998
6994 16998
10669 10767
1369 10767
4745 10767
722 10767
251 16998
3552 16998
7267 16998
1772 16998
18929 10767
9328 10767
3076 10767
14212 10767
284 10767
9599 10767
6137 10767
10565 10767
15137 16998
5349 16998
16431 16998
15719 16998
10917 16998
...

result:

ok AC

Test #21:

score: 0
Accepted
time: 9ms
memory: 5248kb

input:

20000
11262 14400
16805 2790
19084 11979
15259 5949
9916 12236
2445 1637
1905 15141
9540 16655
12812 16186
19052 1523
6643 1443
13738 10091
9218 1337
16617 16436
17295 16466
1171 1217
19150 5280
2830 8076
16135 7234
11460 213
8101 341
5438 6331
5029 14871
10725 2090
5998 12241
8902 3420
4340 7265
18...

output:

14400 19999
16805 19999
13507 15251
5949 15251
9916 15251
2445 15251
15141 15251
16655 15251
16186 15251
1523 15251
1443 15251
10091 15251
9218 15251
16617 15251
16466 15251
1217 15251
19150 15251
2830 15251
7234 15251
11460 15251
8101 15251
6331 15251
14871 15251
10725 15251
12241 15251
8902 15251
...

result:

ok AC

Test #22:

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

input:

20000
19272 1
19272 7240
6952 7240
6952 10594
12564 10594
12564 13132
14483 13132
14483 1891
9772 1891
16614 9772
14519 16614
12050 14519
4039 12050
4039 9679
8408 4039
12050 6797
17990 6797
6797 17659
14519 14985
16415 14985
1735 16415
16415 18821
14985 9402
9402 18947
9402 5386
17560 16614
17560 1...

output:

7240 327
19272 327
6952 327
10594 327
12564 327
13132 327
14483 327
1891 327
9772 327
16614 327
14519 327
12050 327
4039 327
9679 327
8408 327
6797 327
17990 327
17659 327
14985 327
16415 327
1735 327
18821 327
9402 327
18947 327
5386 327
17560 327
1094 327
7537 327
19700 327
9876 327
16466 327
1177...

result:

ok AC

Test #23:

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

input:

20000
4410 1
7210 1
1 2389
4410 18377
4410 4507
7905 4410
7210 14849
12441 7210
7210 9005
17807 2389
2389 6619
2389 6604
6913 18377
5811 18377
7249 18377
4507 1582
4507 8857
4507 17635
10077 7905
7905 4687
8607 7905
14849 16870
14849 3298
14849 2376
12441 9009
12441 10729
19879 12441
9005 19790
7715...

output:

18377 7210
1 18377
2389 18377
4410 7210
4507 7210
7905 7210
14849 18377
12441 18377
9005 18377
17807 18377
6619 18377
6604 18377
6913 7210
5811 7210
7249 7210
1582 7210
8857 7210
17635 7210
10077 7210
4687 7210
8607 7210
16870 18377
3298 18377
2376 18377
9009 18377
10729 18377
19879 18377
19790 1837...

result:

ok AC

Test #24:

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

input:

20000
7223 19213
12395 18674
16451 12980
18029 7848
16056 11920
6906 11077
3923 10662
9192 4837
17604 11135
16462 2457
18842 9770
15130 10251
19601 6770
7954 12079
7559 642
15051 17509
1146 18583
18196 17621
4980 8041
19973 15310
16834 11112
3176 8010
957 12737
4072 830
3194 1873
11400 3394
6914 806...

output:

19213 20000
12395 20000
12980 20000
7848 20000
10423 2808
6906 2808
3923 2808
4837 2808
11135 2808
2457 2808
9770 2808
10251 2808
6770 2808
12079 2808
7559 2808
15051 2808
1146 2808
17621 2808
8041 2808
19973 2808
11112 2808
3176 2808
957 2808
830 2808
3194 2808
11400 2808
6914 2808
14516 2808
15976...

result:

ok AC

Test #25:

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

input:

5
2 1
3 1
4 1
1 5

output:

-1

result:

ok AC

Test #26:

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

input:

20000
1 4794
4794 19823
8249 19823
8249 19672
16549 19672
13478 16549
3608 13478
3608 14623
14623 10303
19353 14623
14623 7999
3608 14367
14367 17910
14367 8488
16947 14367
3608 1121
1121 1836
13048 1121
17393 1121
11488 13478
11488 17346
8954 17346
17346 4922
17346 13440
11488 2278
16202 2278
593 2...

output:

16167 19823
4794 16167
8249 16167
19672 16167
16549 16167
13478 16167
3608 16167
14623 16167
10303 16167
19353 16167
7999 16167
14367 16167
17910 16167
8488 16167
16947 16167
1121 16167
1836 16167
13048 16167
17393 16167
11488 16167
17346 16167
8954 16167
4922 16167
13440 16167
2278 16167
16202 1616...

result:

ok AC

Test #27:

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

input:

20000
1 17253
5390 1
1 10221
1 16259
8902 1
10509 1
1 16551
1 13314
1 12754
1 11707
1 7781
1 2105
1 18132
1 12907
1 5609
1 15234
1 18609
1 13919
1 13882
1 15621
1 1997
1 14002
1 18056
7498 1
13534 1
1530 1
1 14773
1 2001
1 10679
1 13745
6140 1
19975 1
14198 1
1 7536
5623 1
1 6120
1 6954
730 1
1 1601...

output:

5390 3238
1 3238
10221 3238
16259 3238
8902 3238
10509 3238
16551 3238
13314 3238
12754 3238
11707 3238
7781 3238
2105 3238
18132 3238
12907 3238
5609 3238
15234 3238
18609 3238
13919 3238
13882 3238
15621 3238
1997 3238
14002 3238
18056 3238
7498 3238
13534 3238
1530 3238
14773 3238
2001 3238
10679...

result:

ok AC

Test #28:

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

input:

20000
5445 4016
925 12966
8179 19342
5779 1
9123 4530
5079 8720
8754 5478
17667 13748
7203 13819
10489 7645
8537 14929
4717 5427
239 4564
17407 14318
6756 7348
4638 17915
19455 15109
3853 19342
15246 17470
8228 16612
7726 13819
1 16617
16607 6208
6228 12081
1615 14545
11897 16624
7653 14499
7273 195...

output:

5445 19963
12966 19963
8179 19963
7204 16617
9123 7204
5079 7204
5478 7204
13748 7204
7203 7204
7645 7204
14929 7204
4717 7204
4564 7204
14318 7204
7348 7204
17915 7204
15109 7204
3853 7204
15246 7204
8228 7204
7726 7204
1 7204
16607 7204
6228 7204
1615 7204
11897 7204
14499 7204
19530 7204
15437 72...

result:

ok AC

Test #29:

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

input:

20000
1 10558
10558 7298
7298 3082
17807 7298
793 7298
11663 7298
12412 7298
10699 7298
7298 1146
2462 7298
7298 12577
11701 7298
7298 7622
3831 7298
19955 7298
3001 7298
7298 18329
7298 851
7298 16782
7298 17396
7298 15015
12771 7298
7298 10926
4736 7298
9088 7298
4867 7298
16066 7298
7298 2148
729...

output:

11495 7298
10558 11495
3082 11495
17807 11495
793 11495
11663 11495
12412 11495
10699 11495
1146 11495
2462 11495
12577 11495
11701 11495
7622 11495
3831 11495
19955 11495
3001 11495
18329 11495
851 11495
16782 11495
17396 11495
15015 11495
12771 11495
10926 11495
4736 11495
9088 11495
4867 11495
16...

result:

ok AC

Test #30:

score: -100
Wrong Answer
time: 9ms
memory: 6728kb

input:

20000
1 11767
10226 11767
6246 10226
6576 6246
458 6576
458 5997
16052 5997
16052 10900
4370 10900
4370 17480
17480 11379
4859 11379
14663 4859
18363 14663
1454 18363
18490 1454
18490 17760
17760 19850
19832 19850
4252 19832
5482 4252
2802 5482
17779 2802
17779 8601
10844 8601
10844 17372
1230 17372...

output:

1 20000
11767 20000
10226 20000
6246 20000
6576 20000
458 20000
5997 20000
16052 20000
10900 20000
4370 20000
17480 20000
11379 20000
4859 20000
14663 20000
18363 20000
1454 20000
18490 20000
17760 20000
19850 20000
19832 20000
4252 20000
5482 20000
2802 20000
17779 20000
8601 20000
10844 20000
1737...

result:

wrong answer u and v already exists