QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#383295#5545. Contingency Plankevinyang#WA 119ms24216kbC++209.6kb2024-04-09 09:36:272024-04-09 09:36:28

Judging History

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

  • [2024-04-09 09:36:28]
  • 评测
  • 测评结果:WA
  • 用时:119ms
  • 内存:24216kb
  • [2024-04-09 09:36:27]
  • 提交

answer

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

/* Macros {{{ */
/*  A lot of this is from some of Benq's submissions
    [https://codeforces.com/profile/Benq]
    Ugly af to the eyes, but with vim fold its barable
    Hopefully c++20 concepts can make all this stuff must cleaner */

/* Basics {{{ */
using ll = long long;
using ld = long double;
using str = string;

using pi = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;
#define mp make_pair
#define fi first
#define se second

#define arr array
#define ve vector
using vi = vector<int>;
using vll = vector<ll>;
using vld = vector<ld>;

using vpi = vector<pi>;
using vpll = vector<pll>;
using vpld = vector<pld>;

using vvi = vector<vi>;
using vvll = vector<vll>;
using vvld = vector<vld>;

using vvpi = vector<vpi>;
using vvpll = vector<vpll>;
using vvpld = vector<vpld>;

#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define sz size()
#define rsz(a) resize(a)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

#define For(i, a, b) for (int i = a; i < b; ++i)
#define Rof(i, a, b) for (int i = (b)-1; i >= (a); --i)
#define rep(a) For(_, 0, a)
#define each(a, x) for (auto &a : x)
#define reach(a, x) for (auto a = x.rbegin(); a != x.rend(); ++a)

template <typename T, typename U>
inline void cmin(T &x, U y) {
    if (y < x) x = y;
}
template <typename T, typename U>
inline void cmax(T &x, U y) {
    if (x < y) x = y;
}
/*}}}*/

/* IO {{{ */

/* Template Macros {{{ */
#define tcT template <class T
#define tcTU tcT, class U
#define tcTUU tcT, class... U
/*}}}*/

inline namespace Helpers { /*{{{*/
tcT, class = void > struct is_iterable : false_type {};
tcT > struct is_iterable<
          T, void_t<decltype(begin(declval<T>())), decltype(end(declval<T>()))>>
    : true_type {};
tcT > constexpr bool is_iterable_v = is_iterable<T>::value;

tcT, class = void > struct is_readable : false_type {};
tcT > struct is_readable<T, typename std::enable_if_t<is_same_v<
                                decltype(cin >> declval<T &>()), istream &>>>
    : true_type {};
tcT > constexpr bool is_readable_v = is_readable<T>::value;

tcT, class = void > struct is_printable : false_type {};
tcT > struct is_printable<T, typename std::enable_if_t<is_same_v<
                                 decltype(cout << declval<T>()), ostream &>>>
    : true_type {};
tcT > constexpr bool is_printable_v = is_printable<T>::value;
} /* namespace Helpers */
/*}}}*/

inline namespace Input { /*{{{*/
tcT > constexpr bool needs_input_v = !is_readable_v<T> && is_iterable_v<T>;
tcTUU > void re(T &t, U &...u);
tcTU > void re(pair<T, U> &p); /* pairs */

/* re: read{{{ */
tcT > typename enable_if<is_readable_v<T>, void>::type re(T &x) {
    cin >> x;
} /* default */
tcT > typename enable_if<needs_input_v<T>, void>::type re(
          T &i);                                   // vectors, arrays, etc...
tcTU > void re(pair<T, U> &p) { re(p.fi, p.se); }  // pairs
tcT > typename enable_if<needs_input_v<T>, void>::type re(T &i) {
    each(x, i) re(x);
}
tcTUU > void re(T &t, U &...u) {
    re(t);
    re(u...);
} /* read multiple}}} */

/* rv: resize and read vectors{{{ */
void rv(size_t) {}
tcTUU > void rv(size_t N, ve<T> &t, U &...u);
template <class... U>
void rv(size_t, size_t N2, U &...u);
tcTUU > void rv(size_t N, ve<T> &t, U &...u) {
    t.rsz(N);
    re(t);
    rv(N, u...);
}
template <class... U>
void rv(size_t, size_t N2, U &...u) {
    rv(N2, u...);
} /*}}}*/

/* dumb shortcuts to read in ints{{{ */
void decrement() {} /* subtract one from each */
tcTUU > void decrement(T &t, U &...u) {
    --t;
    decrement(u...);
}
#define ints(...)    \
    int __VA_ARGS__; \
    re(__VA_ARGS__);
#define int1(...)      \
    ints(__VA_ARGS__); \
    decrement(__VA_ARGS__); /*}}}*/
} /* namespace Input */
/*}}}*/

inline namespace ToString { /*{{{*/
tcT > constexpr bool needs_output_v = !is_printable_v<T> && is_iterable_v<T>;

/* ts: string representation to print */
tcT > typename enable_if<is_printable_v<T>, str>::type ts(T v) {
    stringstream ss;
    ss << fixed << setprecision(15) << v;
    return ss.str();
} /* default */
tcT > str bit_vec(T t) { /* bit vector to string */
    str res = "{";
    For(i, 0, t.sz) res += ts(t[i]);
    res += "}";
    return res;
}
str ts(ve<bool> v) { return bit_vec(v); }
template <size_t SZ>
str ts(bitset<SZ> b) {
    return bit_vec(b);
} /* bit vector */
tcTU > str ts(pair<T, U> p); /* pairs */
tcT > typename enable_if<needs_output_v<T>, str>::type ts(
          T v); /* vectors, arrays */
tcTU > str ts(pair<T, U> p) { return "(" + ts(p.fi) + ", " + ts(p.se) + ")"; }
tcT > typename enable_if<is_iterable_v<T>, str>::type ts_sep(T v, str sep) {
    /* convert container to string w/ separator sep */
    bool fst = 1;
    str res = "";
    for (const auto &x : v) {
        if (!fst) res += sep;
        fst = 0;
        res += ts(x);
    }
    return res;
}
tcT > typename enable_if<needs_output_v<T>, str>::type ts(T v) {
    return "{" + ts_sep(v, ", ") + "}";
}

/* for nested DS */
template <int, class T>
typename enable_if<!needs_output_v<T>, ve<str>>::type ts_lev(const T &v) {
    return {ts(v)};
}
template <int lev, class T>
typename enable_if<needs_output_v<T>, ve<str>>::type ts_lev(const T &v) {
    if (lev == 0 || !v.sz) return {ts(v)};
    ve<str> res;
    for (const auto &t : v) {
        if (res.sz) res.back() += ",";
        ve<str> tmp = ts_lev<lev - 1>(t);
        res.insert(end(res), all(tmp));
    }
    For(i, 0, res.sz) {
        str bef = " ";
        if (i == 0) bef = "{";
        res[i] = bef + res[i];
    }
    res.back() += "}";
    return res;
}
} /* namespace ToString */
/*}}}*/

inline namespace Output { /*{{{*/
template <class T>
void pr_sep(ostream &os, str, const T &t) {
    os << ts(t);
}
template <class T, class... U>
void pr_sep(ostream &os, str sep, const T &t, const U &...u) {
    pr_sep(os, sep, t);
    os << sep;
    pr_sep(os, sep, u...);
}
/* print w/ no spaces */
template <class... T>
void pr(const T &...t) {
    pr_sep(cout, "", t...);
}
/* print w/ spaces, end with newline */
void ps() { cout << "\n"; }
template <class... T>
void ps(const T &...t) {
    pr_sep(cout, " ", t...);
    ps();
}
/* debug to cerr */
template <class... T>
void dbg_out(const T &...t) {
    pr_sep(cerr, " | ", t...);
    cerr << endl;
}
void loc_info(int line, str names) {
    cerr << "Line(" << line << ") -> [" << names << "]: ";
}
template <int lev, class T>
void dbgl_out(const T &t) {
    cerr << "\n\n" << ts_sep(ts_lev<lev>(t), "\n") << "\n" << endl;
}
} /* namespace Output */
/*}}}}}}}}}*/


// the contegency cables must form a tree
//  the contegency cables 1-(n-2) and cable n-1 must form a tree
//  that is no contegency cables can make a cycle with n-1


// res will be a graph with
//  2(n-1) edges
//  no leafs
//  when processed in dfs order, all edges of type v will have a backedge in the subgraph of type v


// is there some duality here: that is will the initial edges be sufficient back up edges
//  that is, if we delete edge n-1, and all (n-1)', must the graph still be connected

int n;
vpi edges;
map<pi, int> inv_edges;

vi deg;

vvi adj;

vi depth, par;
void dfs(int r, int p=-1, int d=0) {
    par[r] = p, depth[r] = d;
    for(auto c : adj[r]) {
        if(c == p) continue;
        dfs(c, r, d+1);
    }
}

vi par2;
void dfs2(int r, int p=-1) {
    par2[r] = (p == -1) ? p : ((par2[p] == -1) ? p : par2[p]);

    for(auto c : adj[r]) {
        if(c == p) continue;
        dfs(c, r);
    }
}

void solve() {
    re(n), rv(n-1, edges);

    adj.assign(n+1, vi());
    deg.assign(n+1, 0);

    for(int i=0; i<n-1; ++i) {
        auto [u, v] = edges[i];
        ++deg[u], ++deg[v];
        adj[u].pb(v), adj[v].pb(u);
        inv_edges[{u, v}] = i, inv_edges[{v, u}] = i;
    }

    int star_graph = 0;
    for(int i=1; i<=n; ++i) star_graph |= (deg[i] == n-1);
    if(star_graph) { ps(-1); return; }

    auto [a, b] = edges[n-2];
    if(deg[a] == 1 || deg[b] == 1) {

        int leaf = (deg[a] == 1) ? a : b, nleaf = (leaf != a) ? a : b;

        par.resize(n+1), depth.resize(n+1);
        dfs(leaf);

        vpi res(n-1);

        int flag = 1;
        for(int i=1; i<=n; ++i) {

            if(i == leaf || i == nleaf) continue;

            if(flag && (depth[i] >= 3)) {
                res[n-2] = { i, nleaf };
                flag = 0;
            }

            res[inv_edges[{ i, par[i] }]] = { i, leaf };
        }

        for(auto [u, v] : res) ps(u, v);

    } else {

        adj[a].erase(find(all(adj[a]), b));
        adj[b].erase(find(all(adj[b]), a));

        par.resize(n+1), depth.resize(n+1);
        dfs(a), dfs(b);

        par2.resize(n+1);
        dfs2(a), dfs2(b);

        vpi res(n-1);

        for(int i=1; i<=n; ++i) {

            if(i == a || i == b) continue;

            res[inv_edges[{ i, par[i] }]] = { i, (par2[i] != a) ? a : b };
        }

        res[n-2] = { adj[a][0], adj[b][0] };

        for(auto [u, v] : res) ps(u, v);
    }
}

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

    /* cout << fixed << setprecision(6); */
    int t = 1;
    // cin >> t;
    for (int i = 0; i < t; i++) solve();

    return 0;
    // you should actually read the stuff at the bottom
}

/* stuff you should look for
 * int overflow, array bounds
 * special cases (n=1?)
 * do smth instead of nothing and stay organized
 * WRITE STUFF DOWN
 * DON'T GET STUCK ON ONE APPROACH
 */

詳細信息

Test #1:

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

input:

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

output:

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

result:

ok AC

Test #2:

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

input:

3
1 2
2 3

output:

-1

result:

ok AC

Test #3:

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

input:

2
2 1

output:

-1

result:

ok AC

Test #4:

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

input:

5
2 1
2 3
2 4
4 5

output:

1 5
3 5
2 5
1 4

result:

ok AC

Test #5:

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

input:

5
1 4
3 4
4 5
2 5

output:

1 2
3 2
4 2
1 5

result:

ok AC

Test #6:

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

input:

5
5 2
1 2
4 2
3 4

output:

5 3
1 3
2 3
1 4

result:

ok AC

Test #7:

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

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 20000
3 20000
4 20000
5 20000
6 20000
7 20000
8 20000
9 20000
10 20000
11 20000
12 20000
13 20000
14 20000
15 20000
16 20000
17 20000
18 20000
19 20000
20 20000
21 20000
22 20000
23 20000
24 20000
25 20000
26 20000
27 20000
28 20000
29 20000
30 20000
31 20000
32 20000
33 20000
34 20000
35 20000
36...

result:

ok AC

Test #8:

score: 0
Accepted
time: 21ms
memory: 7432kb

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 17029
9205 17029
5971 17029
9886 17029
18853 17029
14108 17029
998 17029
14958 17029
7100 17029
2670 17029
18493 17029
13838 17029
4644 17029
2139 17029
18540 17029
14081 17029
16836 17029
9357 17029
245 17029
242 17029
13472 17029
1471 17029
3792 17029
17875 17029
13976 17029
15085 17029
17283...

result:

ok AC

Test #9:

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

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 18216
15635 18216
8088 18216
12138 18216
12367 18216
15051 18216
6392 18216
15564 18216
17334 18216
10164 18216
8704 18216
13795 18216
10292 18216
12108 18216
50 18216
4 18216
18364 18216
13341 18216
19203 18216
3017 18216
5133 18216
3499 18216
19202 18216
10304 18216
12975 18216
17220 18216
17...

result:

ok AC

Test #10:

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

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 20000
3 20000
4 20000
5 20000
6 20000
7 20000
8 20000
9 20000
10 20000
11 20000
12 20000
13 20000
14 20000
15 20000
16 20000
17 20000
18 20000
19 20000
20 20000
21 20000
22 20000
23 20000
24 20000
25 20000
26 20000
27 20000
28 20000
29 20000
30 20000
31 20000
32 20000
33 20000
34 20000
35 20000
36...

result:

ok AC

Test #11:

score: 0
Accepted
time: 21ms
memory: 7556kb

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 19555
19998 19555
3314 19555
3339 19555
10237 19555
13244 19555
3392 19555
4459 19555
17335 19555
10356 19555
6124 19555
4470 19555
12896 19555
12094 19555
3309 19555
13319 19555
15658 19555
2305 19555
13710 19555
16520 19555
16234 19555
6697 19555
6686 19555
9187 19555
43 19555
2764 19555
9061 19...

result:

ok AC

Test #12:

score: 0
Accepted
time: 21ms
memory: 7396kb

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 9353
1206 9353
8947 9353
4887 9353
14605 9353
2947 9353
9038 9353
5326 9353
9021 9353
11087 9353
19562 9353
895 9353
14653 9353
10803 9353
9750 9353
16331 9353
4689 9353
14307 9353
11631 9353
13244 9353
10554 9353
8112 9353
9394 9353
5945 9353
15279 9353
15512 9353
1334 9353
6025 9353
19566 935...

result:

ok AC

Test #13:

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

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 100000
3 100000
4 100000
5 100000
6 100000
7 100000
8 100000
9 100000
10 100000
11 100000
12 100000
13 100000
14 100000
15 100000
16 100000
17 100000
18 100000
19 100000
20 100000
21 100000
22 100000
23 100000
24 100000
25 100000
26 100000
27 100000
28 100000
29 100000
30 100000
31 100000
32 10000...

result:

ok AC

Test #14:

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

input:

5
2 1
3 2
4 3
5 4

output:

1 5
2 5
3 5
1 4

result:

ok AC

Test #15:

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

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 99803
13678 99803
27196 99803
70437 99803
35891 99803
43010 99803
28018 99803
64489 99803
61157 99803
35572 99803
41613 99803
73049 99803
93865 99803
83507 99803
92127 99803
86278 99803
15004 99803
44154 99803
2005 99803
94210 99803
41410 99803
5886 99803
69836 99803
24120 99803
80802 99803
99...

result:

ok AC

Test #16:

score: 0
Accepted
time: 110ms
memory: 24144kb

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 78172
28108 78172
87682 78172
79359 78172
16128 78172
90652 78172
55874 78172
27276 78172
66899 78172
10296 78172
37870 78172
78978 78172
26221 78172
28589 78172
46430 78172
32252 78172
22407 78172
68230 78172
64944 78172
53457 78172
31023 78172
57101 78172
82578 78172
33273 78172
69683 78172
...

result:

ok AC

Test #17:

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

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 100000
3 100000
4 100000
5 100000
6 100000
7 100000
8 100000
9 100000
10 100000
11 100000
12 100000
13 100000
14 100000
15 100000
16 100000
17 100000
18 100000
19 100000
20 100000
21 100000
22 100000
23 100000
24 100000
25 100000
26 100000
27 100000
28 100000
29 100000
30 100000
31 100000
32 10000...

result:

ok AC

Test #18:

score: 0
Accepted
time: 118ms
memory: 24176kb

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 26907
13919 26907
86413 26907
78418 26907
36904 26907
60478 26907
78563 26907
23855 26907
63531 26907
15574 26907
73713 26907
62532 26907
19461 26907
80750 26907
57012 26907
27046 26907
55780 26907
69619 26907
58970 26907
65824 26907
3195 26907
26782 26907
71411 26907
84915 26907
95347 26907
53739...

result:

ok AC

Test #19:

score: 0
Accepted
time: 109ms
memory: 24164kb

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 86919
51514 86919
83613 86919
16333 86919
25291 86919
61711 86919
37621 86919
66805 86919
59550 86919
67744 86919
46644 86919
21771 86919
98164 86919
6655 86919
75053 86919
90431 86919
58023 86919
48769 86919
11506 86919
19125 86919
52852 86919
98702 86919
53360 86919
3999 86919
66767 86919
82...

result:

ok AC

Test #20:

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

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:

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

result:

ok AC

Test #21:

score: 0
Accepted
time: 23ms
memory: 7524kb

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 5679
16805 5679
11979 5679
5949 5679
9916 5679
2445 5679
15141 5679
16655 5679
16186 5679
1523 5679
1443 5679
10091 5679
9218 5679
16617 5679
16466 5679
1217 5679
19150 5679
2830 5679
7234 5679
11460 5679
8101 5679
6331 5679
14871 5679
10725 5679
12241 5679
8902 5679
7265 5679
5618 5679
14867 ...

result:

ok AC

Test #22:

score: 0
Accepted
time: 17ms
memory: 7304kb

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:

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

result:

ok AC

Test #23:

score: 0
Accepted
time: 21ms
memory: 7316kb

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:

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

result:

ok AC

Test #24:

score: -100
Wrong Answer
time: 23ms
memory: 7392kb

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 16305
12395 16305
12980 16305
7848 16305
11920 16305
6906 16305
3923 16305
4837 16305
11135 16305
2457 16305
9770 16305
10251 16305
6770 16305
12079 16305
7559 16305
15051 16305
1146 16305
17621 16305
8041 16305
19973 16305
11112 16305
3176 16305
957 16305
830 16305
3194 16305
11400 16305
6914...

result:

wrong answer u and v already exists