QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#180991#5545. Contingency PlancsyptWA 28ms14880kbC++142.2kb2023-09-16 14:55:522023-09-16 14:55:52

Judging History

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

  • [2023-09-16 14:55:52]
  • 评测
  • 测评结果:WA
  • 用时:28ms
  • 内存:14880kb
  • [2023-09-16 14:55:52]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define X first
#define Y second
typedef pair<int, int> pii;

const int N = 1e5 + 5;
int n;
vector<pii> edge;
vector<int> g[N];
int par[N], mark[N];

pii bfs(int u) {
  queue<pii> q;
  vector<int> vis(n + 1, 0);
  vis[u] = 1;
  q.push({u, 0});
  int len = 0, end = u;
  while (!q.empty()) {
    auto [v, dis] = q.front();
    q.pop();
    for (int x : g[v]) {
      if (!vis[x]) {
        vis[x] = 1;
        q.push({x, dis + 1});
        if (dis + 1 > len) {
          len = dis + 1;
          end = x;
        }
      }
    }
  }
  return {len, end};
}

void dfs(int u, int p) {
  par[u] = p;
  for (int v : g[u]) {
    if (v != p) dfs(v, u);
  }
}

void solve() {
  cin >> n;
  for (int i = 0, u, v; i < n - 1; i++) {
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
    edge.push_back({u, v});
  }
  int root = bfs(1).Y;
  auto [dia, leaf] = bfs(root);
  if (dia <= 2) {
    cout << "-1\n";
    return;
  }
  dfs(root, 0);
  int child;
  for (int i = 1; i <= n; i++) {
    if (par[i] == root) child = i;
  }
  for (int i = 0; i < n - 1; i++) {
    if (par[edge[i].X] == edge[i].Y) swap(edge[i].X, edge[i].Y);
  }
  int x = leaf;
  while (x != root) {
    mark[x] = 1;
    x = par[x];
  }
  bool flag1 = 0, flag2 = 0;
  for (int i = 0; i < n - 1; i++) {
    auto [a, b] = edge[i];
    if (flag1) {
      if (flag2 && mark[b]) {
        if (a == child) {
          cout << a << " " << leaf << "\n";
        } else {
          cout << a << " " << root << "\n";
        }
      } else {
        if (b == child) {
          cout << b << " " << leaf << "\n";
        } else {
          cout << b << " " << root << "\n";
        }
      }
    }
    else {
      if (mark[b]) {
        flag1 = true;
        if (b == child) {
          flag2 = true;
          cout << a << " " << child << "\n";
        } else {
          flag2 = false;
          cout << b << " " << root << "\n";
        }
      } else {
        cout << b << " " << root << "\n";
      }
    }
  }
}

signed main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int T = 1;
  // cin >> T;
  while (T--) solve();
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

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

result:

ok AC

Test #2:

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

input:

3
1 2
2 3

output:

-1

result:

ok AC

Test #3:

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

input:

2
2 1

output:

-1

result:

ok AC

Test #4:

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

input:

5
2 1
2 3
2 4
4 5

output:

1 5
3 5
2 5
4 1

result:

ok AC

Test #5:

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

input:

5
1 4
3 4
4 5
2 5

output:

1 2
3 2
4 2
5 1

result:

ok AC

Test #6:

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

input:

5
5 2
1 2
4 2
3 4

output:

5 3
1 3
2 3
4 5

result:

ok AC

Test #7:

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

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: 6ms
memory: 7348kb

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: 3ms
memory: 7344kb

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: 3ms
memory: 7812kb

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: 7ms
memory: 8324kb

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: 7ms
memory: 8296kb

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: 22ms
memory: 14172kb

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: 6908kb

input:

5
2 1
3 2
4 3
5 4

output:

1 5
2 5
3 5
4 1

result:

ok AC

Test #15:

score: 0
Accepted
time: 27ms
memory: 14880kb

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: 24ms
memory: 14756kb

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: 26ms
memory: 14528kb

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: 28ms
memory: 14316kb

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: 23ms
memory: 14680kb

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: 3ms
memory: 7820kb

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 12158
10767 12158
13211 12158
495 12158
7635 12158
6994 12158
16998 12158
1369 12158
4745 12158
722 12158
251 12158
3552 12158
7267 12158
1772 12158
10669 12158
9328 12158
3076 12158
14212 12158
284 12158
9599 12158
6137 12158
10565 12158
15137 12158
5349 12158
16431 12158
15719 12158
10917 12158
...

result:

ok AC

Test #21:

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

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

result:

ok AC

Test #22:

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

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:

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

result:

ok AC

Test #23:

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

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:

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

result:

ok AC

Test #24:

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

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

result:

ok AC

Test #25:

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

input:

5
2 1
3 1
4 1
1 5

output:

-1

result:

ok AC

Test #26:

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

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:

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

result:

ok AC

Test #27:

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

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:

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

result:

ok AC

Test #28:

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

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 15437
12966 15437
8179 15437
5779 15437
9123 15437
5079 15437
5478 15437
13748 15437
7203 15437
7645 15437
14929 15437
4717 15437
4564 15437
14318 15437
7348 15437
17915 15437
15109 15437
3853 15437
15246 15437
8228 15437
7726 15437
16617 15437
16607 15437
6228 15437
1615 15437
11897 15437
1449...

result:

ok AC

Test #29:

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

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:

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

result:

ok AC

Test #30:

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

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 4129
11767 4129
10226 4129
6246 4129
6576 4129
458 4129
5997 4129
16052 4129
10900 4129
4370 4129
17480 4129
11379 4129
4859 4129
14663 4129
18363 4129
1454 4129
18490 4129
17760 4129
19850 4129
19832 4129
4252 4129
5482 4129
2802 4129
17779 4129
8601 4129
10844 4129
17372 4129
1230 4129
13019 412...

result:

ok AC

Test #31:

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

input:

20000
16653 18166
1123 17313
12716 14313
11207 7401
2794 831
480 7420
4462 1161
575 456
15192 3052
12389 7101
15729 18976
18772 19492
18805 2052
866 10412
8160 3697
13319 15062
19241 11526
11876 3502
613 17770
15035 14829
6518 16531
11665 19122
15722 18062
19841 14843
5758 3123
1633 14519
3637 13277...

output:

16653 9780
1123 9780
12716 9780
7401 9780
2794 9780
480 9780
4462 9780
575 9780
15192 9780
12389 9780
15729 9780
19492 9780
2052 9780
866 9780
3697 9780
13319 9780
19241 9780
3502 9780
17770 9780
15035 9780
6518 9780
19122 9780
18062 9780
14843 9780
3123 9780
1633 9780
13277 9780
16195 9780
18042 97...

result:

ok AC

Test #32:

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

input:

20000
5613 1
1 999
1 16709
1 2491
9549 1
19706 1
1 1022
1 3884
1 1916
6627 1
1 1600
10265 1
1 19100
19766 1
1 7450
1 14375
5986 1
10295 1
8625 1
11810 1
1 15542
1 5745
3506 1
12842 1
1 11860
1 16317
1 6553
12476 1
1 6031
8445 1
6462 1
1 1601
1 3014
14100 1
1 6771
1 2360
1 15402
4549 1
6116 1
1 17848...

output:

-1

result:

ok AC

Test #33:

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

input:

20000
2509 13795
17043 13795
12006 13795
13795 822
3022 13795
8572 13795
2579 13795
13795 9673
12654 13795
4181 13795
13795 15912
13795 8902
13795 19201
5015 13795
243 13795
13795 6524
13795 9461
16403 13795
13795 18444
1316 13795
15366 13795
13795 17126
13795 309
13795 10938
13795 1255
13795 5588
1...

output:

-1

result:

ok AC

Test #34:

score: -100
Wrong Answer
time: 8ms
memory: 7564kb

input:

20000
12144 2902
8713 11740
8870 10266
6116 3885
5943 8380
10496 956
14162 9193
4497 3275
5480 4601
6858 17285
1067 3003
19501 1958
5579 12167
844 12167
5372 16648
18876 13545
6559 10656
2910 6918
5632 16656
10135 11948
11253 13524
10068 15948
17884 3833
6830 16257
1248 6924
9806 14359
11033 8077
86...

output:

12144 3838
8713 3838
10266 3838
6116 3838
5943 3838
10496 3838
9193 3838
4497 3838
5480 3838
6858 3838
3003 3838
1958 3838
5579 3838
12167 3838
16648 3838
18876 3838
10656 3838
6918 3838
5632 3838
10135 3838
11253 3838
10068 3838
3833 3838
16257 3838
6924 3838
9806 3838
8077 3838
8650 3838
9461 3838...

result:

wrong answer u and v already exists