QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#699037#5545. Contingency PlanTheZoneAC ✓56ms15416kbC++202.2kb2024-11-01 23:56:152024-11-01 23:56:16

Judging History

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

  • [2024-11-01 23:56:16]
  • 评测
  • 测评结果:AC
  • 用时:56ms
  • 内存:15416kb
  • [2024-11-01 23:56:15]
  • 提交

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 << " " << leaf << "\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: 3856kb

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

input:

3
1 2
2 3

output:

-1

result:

ok AC

Test #3:

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

input:

2
2 1

output:

-1

result:

ok AC

Test #4:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

input:

5
2 1
3 1
4 1
1 5

output:

-1

result:

ok AC

Test #26:

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

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

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

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

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

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

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

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

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: 0
Accepted
time: 6ms
memory: 5396kb

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:

ok AC

Test #35:

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

input:

20000
1284 10854
1436 9770
17852 14859
19561 13068
19123 19730
8297 15453
7167 3888
5853 15710
18440 5611
9368 5242
6667 12315
19899 12021
13550 19105
16314 1977
18051 11095
4122 16348
1987 4873
14613 10548
375 11649
6442 1199
228 18390
4006 7870
2115 10763
13056 1980
4042 9649
11446 10078
14111 289...

output:

1284 6315
1436 6315
17852 6315
13068 6315
19730 6315
15453 6315
3888 6315
5853 6315
18440 6315
5242 6315
12315 6315
12021 6315
19105 6315
1977 6315
11095 6315
4122 6315
4873 6315
10548 6315
11649 6315
1199 6315
228 6315
4006 6315
10763 6315
1980 6315
9649 6315
11446 6315
14111 6315
14896 6315
6991 6...

result:

ok AC

Test #36:

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

input:

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

output:

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

result:

ok AC

Test #37:

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

input:

20000
1 1914
16448 1914
16448 447
1 19785
19232 19785
17236 19785
12409 17236
11707 12409
15526 11707
15526 12645
19367 12645
19367 7871
12617 7871
658 7871
2936 7871
10186 2936
10186 12483
4222 12483
4222 6106
3280 6106
7313 6106
17305 6106
2244 17305
17305 18735
16748 6106
16748 1554
16748 1261
73...

output:

1914 4567
16448 4567
447 4567
1 4567
19232 4567
19785 4567
17236 4567
12409 4567
15526 4567
12645 4567
19367 4567
7871 4567
12617 4567
658 4567
2936 4567
10186 4567
12483 4567
4222 4567
6106 4567
3280 4567
7313 4567
17305 4567
2244 4567
18735 4567
16748 4567
1554 4567
1261 4567
7318 4567
9524 4567
7...

result:

ok AC

Test #38:

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

input:

20000
8234 1
16079 8234
18825 16079
18825 12361
12361 6709
6709 10905
12205 10905
3916 12205
16311 3916
16423 16311
16423 10094
10094 9710
1474 9710
1474 18631
18631 13459
6640 13459
19380 6640
19380 6320
19874 6320
2212 19874
2212 8880
8880 2809
15348 2809
14869 15348
14869 8029
924 8029
924 10270
...

output:

1 93
8234 93
16079 93
18825 93
12361 93
6709 93
10905 93
12205 93
3916 93
16311 93
16423 93
10094 93
9710 93
1474 93
18631 93
13459 93
6640 93
19380 93
6320 93
19874 93
2212 93
8880 93
2809 93
15348 93
14869 93
8029 93
924 93
10270 93
16526 93
4694 93
1818 93
15046 93
10755 93
124 93
8951 93
3035 93...

result:

ok AC

Test #39:

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

input:

20000
3828 10203
17892 5873
17224 10321
12241 7554
2948 6507
17619 16861
11410 1012
17019 18616
13582 19398
16411 15552
578 14161
9621 19542
9684 1699
16733 9223
16474 19501
15178 3217
9743 11111
6539 14379
5655 12001
10637 2251
13411 7006
7104 9228
15833 19339
12622 4315
19092 7490
8033 12870
19399...

output:

3828 6157
5873 6157
17224 6157
7554 6157
6507 6157
17619 6157
1012 6157
18616 6157
19398 6157
16411 6157
578 6157
9621 6157
9684 6157
16733 6157
19501 6157
3217 6157
11111 6157
6539 6157
12001 6157
2251 6157
13411 6157
9228 6157
15833 6157
4315 6157
19092 6157
8033 6157
1103 6157
12722 6157
5264 615...

result:

ok AC

Test #40:

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

input:

20000
6712 1
6712 16871
8572 16871
8572 10641
10641 16702
16702 18095
14014 18095
14014 10577
10577 1956
1956 13463
4593 13463
4593 17604
8524 17604
8524 4625
4625 5906
5906 17983
17983 13029
13029 7366
13038 7366
13038 3804
3804 3699
3699 15717
15717 967
16443 967
16443 1797
3079 1797
9213 3079
232...

output:

1 11358
6712 11358
16871 11358
8572 11358
10641 11358
16702 11358
18095 11358
14014 11358
10577 11358
1956 11358
13463 11358
4593 11358
17604 11358
8524 11358
4625 11358
5906 11358
17983 11358
13029 11358
7366 11358
13038 11358
3804 11358
3699 11358
15717 11358
967 11358
16443 11358
1797 11358
3079 ...

result:

ok AC

Test #41:

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

input:

20000
2591 11751
5562 1300
9597 7814
11201 6762
9942 6089
18201 10054
14040 17666
14050 3479
2754 6286
5122 10070
2705 10053
3703 8076
33 13628
18330 17144
15031 16159
668 10414
14591 4857
15396 13207
6623 13987
3946 9270
15622 17484
4063 8811
12866 7551
3439 8748
10982 6076
15522 1678
8947 4749
677...

output:

11751 13400
1300 13400
9597 13400
11201 13400
9942 13400
10054 13400
14040 13400
14050 13400
6286 13400
10070 13400
10053 13400
8076 13400
33 13400
18330 13400
16159 13400
668 13400
4857 13400
15396 13400
6623 13400
9270 13400
17484 13400
4063 13400
7551 13400
3439 13400
6076 13400
1678 13400
4749 1...

result:

ok AC

Test #42:

score: 0
Accepted
time: 37ms
memory: 13440kb

input:

100000
1 72500
1 89151
72500 50542
16422 72500
31678 89151
89151 54297
19071 50542
25039 50542
59896 16422
57305 16422
17263 31678
31678 3514
54297 25341
13381 54297
19071 7507
15806 19071
25039 62775
20433 25039
59896 28013
59896 2793
84857 57305
57305 84225
17263 6434
17263 61853
37741 3514
3514 8...

output:

1 58704
89151 58704
72500 58704
16422 58704
31678 58704
54297 58704
50542 58704
25039 58704
59896 58704
57305 58704
17263 58704
3514 58704
25341 58704
13381 58704
19071 58704
15806 58704
62775 58704
20433 58704
28013 58704
2793 58704
84857 58704
84225 58704
6434 58704
61853 58704
37741 58704
83001 5...

result:

ok AC

Test #43:

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

input:

100000
37174 25594
26356 56758
70911 5299
53571 20298
89704 67180
69629 74497
31785 14492
10546 1814
71677 54029
2466 28838
57294 23003
35667 41920
5998 95159
14430 34895
74794 85483
87138 10195
54295 96087
21621 26770
92353 70922
56725 17254
67745 92044
30390 34948
64685 31050
54736 78533
63644 859...

output:

37174 28376
26356 28376
70911 28376
20298 28376
89704 28376
74497 28376
14492 28376
10546 28376
71677 28376
28838 28376
23003 28376
41920 28376
95159 28376
34895 28376
74794 28376
10195 28376
54295 28376
21621 28376
70922 28376
56725 28376
67745 28376
30390 28376
31050 28376
78533 28376
8591 28376
4...

result:

ok AC

Test #44:

score: 0
Accepted
time: 37ms
memory: 13348kb

input:

100000
90403 1
90403 84049
84049 28339
50038 28339
50038 23735
23735 87291
87291 26404
26404 3276
3276 37488
67144 37488
67144 15335
15335 73596
32815 73596
58348 32815
32340 58348
77042 32340
32340 17210
58348 68281
68281 13360
68281 52957
32815 3781
88746 3781
33513 88746
88746 23338
11895 3781
90...

output:

1 77042
90403 77042
84049 77042
28339 77042
50038 77042
23735 77042
87291 77042
26404 77042
3276 77042
37488 77042
67144 77042
15335 77042
73596 77042
32815 77042
58348 77042
32340 51949
17210 77042
68281 77042
13360 77042
52957 77042
3781 77042
88746 77042
33513 77042
23338 77042
11895 77042
90021 ...

result:

ok AC

Test #45:

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

input:

100000
10753 1
31716 1
1 8354
41344 10753
10753 22340
33736 10753
31716 74747
24655 31716
31716 93736
4454 8354
65308 8354
36992 8354
53743 41344
59301 41344
41344 86462
22340 77782
22340 49193
90415 22340
33736 2126
72574 33736
33736 98153
92064 74747
23614 74747
74747 96121
24655 95702
47727 24655...

output:

1 89646
31716 89646
8354 89646
10753 89646
22340 89646
33736 89646
74747 89646
24655 89646
93736 89646
4454 89646
65308 89646
36992 89646
41344 89646
59301 89646
86462 89646
77782 89646
49193 89646
90415 89646
2126 89646
72574 89646
98153 89646
92064 89646
23614 89646
96121 89646
95702 89646
47727 8...

result:

ok AC

Test #46:

score: 0
Accepted
time: 37ms
memory: 13500kb

input:

100000
82182 59525
43093 74187
83434 62328
30609 75691
98351 97443
93951 9234
89762 57868
66707 24839
91314 82444
9148 12031
46318 817
9254 56692
67828 19158
29614 79432
64090 86748
43645 44758
91501 26481
13108 70283
53676 76180
2183 16343
17086 64156
13813 38661
1934 69441
21652 50770
62980 13969
...

output:

82182 93454
74187 93454
83434 93454
30609 93454
97443 93454
93951 93454
57868 93454
24839 93454
91314 93454
9148 93454
817 93454
56692 93454
67828 93454
79432 93454
64090 93454
44758 93454
26481 93454
70283 93454
76180 93454
2183 93454
17086 93454
38661 93454
69441 93454
50770 93454
13969 93454
3288...

result:

ok AC

Test #47:

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

input:

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

output:

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

result:

ok AC

Test #48:

score: 0
Accepted
time: 33ms
memory: 13728kb

input:

100000
1 59819
46211 59819
46211 78631
78631 6887
6887 15685
45496 15685
45496 38399
38399 43932
22491 43932
22491 57782
25655 57782
57782 81578
40906 57782
22491 8185
8185 92518
96199 8185
63790 8185
22491 64847
84427 64847
34665 64847
30015 64847
34952 43932
34952 12997
41447 12997
19357 12997
307...

output:

1 25655
59819 25655
46211 25655
78631 25655
6887 25655
15685 25655
45496 25655
38399 25655
43932 25655
22491 25655
57782 17159
81578 25655
40906 25655
8185 25655
92518 25655
96199 25655
63790 25655
64847 25655
84427 25655
34665 25655
30015 25655
34952 25655
12997 25655
41447 25655
19357 25655
30750 ...

result:

ok AC

Test #49:

score: 0
Accepted
time: 31ms
memory: 14596kb

input:

100000
70720 1
71027 1
48338 1
1 61809
1 79963
1 39740
86644 1
14939 1
39918 1
41470 1
23364 1
1 54664
1 96370
1 53835
1 67313
33696 1
44243 1
50423 1
1 70539
73776 1
560 1
98363 1
71623 1
72365 1
1 73548
1 82843
1 64083
52686 1
1 44452
1 94601
1 43725
88136 1
1 65340
30989 1
1 94282
76705 1
1 4208
...

output:

1 49673
71027 49673
48338 49673
61809 49673
79963 49673
39740 49673
86644 49673
14939 49673
39918 49673
41470 49673
23364 49673
54664 49673
96370 49673
53835 49673
67313 49673
33696 49673
44243 49673
50423 49673
70539 49673
73776 49673
560 49673
98363 49673
71623 49673
72365 49673
73548 49673
82843 ...

result:

ok AC

Test #50:

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

input:

100000
55448 49209
4084 16405
52470 22193
57007 13008
43787 82824
91893 67413
72105 89438
5791 85302
74502 44950
57906 11997
53465 42216
63894 41770
20892 54078
19530 68055
34937 22893
43941 47065
54015 53196
91519 81132
80483 71834
1399 53196
18226 23550
46619 51969
78131 47878
85576 60764
37319 88...

output:

55448 32747
4084 32747
22193 32747
13008 32747
82824 32747
91893 32747
72105 32747
5791 32747
44950 32747
11997 32747
42216 32747
41770 32747
20892 32747
68055 32747
22893 32747
47065 32747
54015 32747
91519 32747
80483 32747
1399 32747
23550 32747
46619 32747
47878 32747
85576 32747
37319 32747
321...

result:

ok AC

Test #51:

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

input:

100000
1 13485
13485 21238
21238 89751
21238 74621
14404 21238
60040 21238
21238 46089
46928 21238
73214 21238
88224 21238
47403 21238
21238 99205
89778 21238
21238 89464
22870 21238
21238 75159
40123 21238
33512 21238
21238 30257
70298 21238
21238 79591
57804 21238
21238 99840
64087 21238
12717 212...

output:

1 89751
13485 89751
21238 55772
74621 89751
14404 89751
60040 89751
46089 89751
46928 89751
73214 89751
88224 89751
47403 89751
99205 89751
89778 89751
89464 89751
22870 89751
75159 89751
40123 89751
33512 89751
30257 89751
70298 89751
79591 89751
57804 89751
99840 89751
64087 89751
12717 89751
8059...

result:

ok AC

Test #52:

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

input:

100000
43730 1
43730 8413
8413 13508
53025 13508
44444 53025
44444 46747
54535 46747
54535 16058
16058 27066
27066 73721
35961 73721
18398 35961
18398 3188
3188 9998
57229 9998
57229 96831
2109 96831
2109 89059
89059 89520
89520 62512
62512 9136
9136 32949
27353 32949
19993 27353
19993 17305
91005 1...

output:

1 91469
43730 91469
8413 91469
13508 91469
53025 91469
44444 91469
46747 91469
54535 91469
16058 91469
27066 91469
73721 91469
35961 91469
18398 91469
3188 91469
9998 91469
57229 91469
96831 91469
2109 91469
89059 91469
89520 91469
62512 91469
9136 91469
32949 91469
27353 91469
19993 91469
17305 914...

result:

ok AC

Test #53:

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

input:

100000
5616 54215
70847 24268
13256 88765
87054 72678
65173 1284
61132 24104
29759 37270
50005 62107
8909 58386
97772 68628
3463 41963
93835 10608
7780 68599
97385 40426
52295 15155
65521 84045
97372 22218
24089 69011
44236 64952
21273 33469
21618 31458
76924 4738
27278 21658
6790 18294
2343 82355
8...

output:

5616 42980
70847 42980
13256 42980
87054 42980
65173 42980
24104 42980
29759 42980
62107 42980
58386 42980
68628 42980
41963 42980
93835 42980
68599 42980
40426 42980
52295 42980
84045 42980
22218 42980
24089 42980
64952 42980
21273 42980
21618 42980
76924 42980
27278 42980
6790 42980
82355 42980
88...

result:

ok AC

Test #54:

score: 0
Accepted
time: 13ms
memory: 13420kb

input:

100000
1 81565
21567 1
86484 1
95714 1
1 93565
1 15812
51087 1
15941 1
36746 1
1 34149
1 71887
1 61269
1 93111
1 52394
8732 1
1 62378
1 74176
1362 1
15806 1
91535 1
1 77121
1 17356
1 23401
70673 1
1 21367
77472 1
1 44692
1 45094
1 43652
62628 1
1 81187
1 98635
2258 1
1 491
1 1963
1 83580
12393 1
1 5...

output:

-1

result:

ok AC

Test #55:

score: 0
Accepted
time: 16ms
memory: 13396kb

input:

100000
62999 54230
62172 54230
54230 87813
80978 54230
54230 13635
8808 54230
34109 54230
54230 13451
54230 30179
9847 54230
93260 54230
54230 45610
54230 7282
54230 42958
54230 54480
54230 62452
54230 95890
32418 54230
54230 8456
54230 64404
54230 40018
54230 70843
38010 54230
57364 54230
95022 542...

output:

-1

result:

ok AC

Test #56:

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

input:

100000
85431 10525
82137 81079
48778 58755
215 90110
51120 51131
16823 69899
6320 72931
65015 30930
68354 78098
32070 13344
55633 13621
69157 69872
92675 79903
96312 24145
13234 89857
62310 15217
7671 50027
34561 73029
90324 42836
14988 3767
96314 18015
665 82164
49080 34432
24022 62814
89664 13182
...

output:

85431 57788
81079 57788
48778 57788
215 57788
51131 57788
16823 57788
72931 57788
30930 57788
78098 57788
13344 57788
13621 57788
69157 57788
79903 57788
24145 57788
13234 57788
15217 57788
7671 57788
73029 57788
90324 57788
3767 57788
18015 57788
665 57788
49080 57788
24022 57788
13182 57788
34581 ...

result:

ok AC

Test #57:

score: 0
Accepted
time: 41ms
memory: 13040kb

input:

100000
54861 12509
16932 42872
34657 39417
13373 37054
53410 71695
2271 28730
77047 80422
7187 34867
94140 69441
47384 90599
15092 60892
94502 35186
58059 98865
46037 92080
96465 56648
81008 245
86644 72226
35703 96730
7922 3613
97616 90536
41294 92557
22776 10335
74308 16656
86493 81735
91472 93048...

output:

12509 68539
42872 68539
34657 68539
37054 68539
53410 68539
28730 68539
77047 68539
7187 68539
94140 68539
47384 68539
60892 68539
35186 68539
98865 68539
46037 68539
96465 68539
245 68539
86644 68539
96730 68539
3613 68539
97616 68539
41294 68539
22776 68539
74308 68539
81735 68539
93048 68539
7645...

result:

ok AC

Test #58:

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

input:

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

output:

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

result:

ok AC

Test #59:

score: 0
Accepted
time: 35ms
memory: 12928kb

input:

100000
88390 1
1 51242
1 73844
73844 82993
69357 82993
82993 89153
89153 92016
36977 89153
75137 36977
82993 53533
97404 53533
49989 97404
67125 49989
53533 7006
7006 63635
60387 7006
59312 60387
24309 59312
26526 24309
24309 9985
9985 26403
60387 55203
55203 79993
79993 71230
71230 52071
52071 8306...

output:

88390 96661
51242 96661
1 96661
73844 96661
69357 96661
89153 96661
92016 96661
36977 96661
75137 96661
82993 96661
97404 96661
49989 96661
67125 96661
53533 96661
63635 96661
60387 96661
59312 96661
24309 96661
26526 96661
9985 96661
26403 96661
55203 96661
79993 96661
71230 96661
52071 96661
83065...

result:

ok AC

Test #60:

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

input:

100000
1 7264
7264 69649
85097 69649
29848 85097
29848 68683
68683 42523
15272 42523
97689 15272
97689 7996
30390 7996
54151 30390
22264 54151
22264 98123
98123 16751
27570 16751
9987 27570
9987 86950
86950 67445
67445 87275
8871 87275
8871 74967
74967 53362
53362 10217
10217 52404
45262 52404
45262...

output:

1 82119
7264 82119
69649 82119
85097 82119
29848 82119
68683 82119
42523 82119
15272 82119
97689 82119
7996 82119
30390 82119
54151 82119
22264 82119
98123 82119
16751 82119
27570 82119
9987 82119
86950 82119
67445 82119
87275 82119
8871 82119
74967 82119
53362 82119
10217 82119
52404 82119
45262 82...

result:

ok AC

Test #61:

score: 0
Accepted
time: 37ms
memory: 13124kb

input:

100000
3518 47523
14887 83452
31336 87320
47772 87482
71420 24559
99732 17539
45904 20872
52728 70439
38581 75203
18345 49294
7385 74056
95971 72826
48547 37020
61306 27212
53241 59530
32550 2892
5369 8488
4000 50453
45119 41435
5899 77096
19235 37917
75044 40239
44198 79848
23637 99807
40855 52471
...

output:

3518 94532
14887 94532
87320 94532
87482 94532
71420 94532
99732 94532
20872 94532
70439 94532
38581 94532
49294 94532
7385 94532
95971 94532
37020 94532
61306 94532
53241 94532
2892 94532
8488 94532
50453 94532
45119 94532
77096 94532
37917 94532
40239 94532
79848 94532
99807 94532
52471 94532
2456...

result:

ok AC

Test #62:

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

input:

100000
56405 1
56405 66063
66801 66063
66801 9845
9845 42911
42911 64818
67482 64818
35942 67482
35942 75546
75546 4505
4505 45628
45628 29159
29159 29378
83665 29378
83665 85205
85205 94326
78400 94326
91544 78400
92293 91544
95489 92293
20854 95489
20854 94810
91796 94810
91796 49331
49331 66242
9...

output:

1 12009
56405 12009
66063 12009
66801 12009
9845 12009
42911 12009
64818 12009
67482 12009
35942 12009
75546 12009
4505 12009
45628 12009
29159 12009
29378 12009
83665 12009
85205 12009
94326 12009
78400 12009
91544 12009
92293 12009
95489 12009
20854 12009
94810 12009
91796 12009
49331 12009
66242 ...

result:

ok AC

Test #63:

score: 0
Accepted
time: 49ms
memory: 14408kb

input:

100000
29993 41605
84963 10140
60237 62389
66780 93449
98439 1174
75487 87344
56945 1098
7281 10192
90231 22033
95031 94597
88728 56965
74791 64971
68584 15462
91264 43556
80943 25018
89575 23985
46970 91618
7237 89928
26433 7488
10258 93471
44420 34919
39007 60649
64537 14238
89107 56906
58805 7576...

output:

41605 55130
84963 55130
60237 55130
93449 55130
98439 55130
75487 55130
1098 55130
7281 55130
90231 55130
95031 55130
56965 55130
64971 55130
68584 55130
91264 55130
80943 55130
89575 55130
46970 55130
89928 55130
26433 55130
10258 55130
44420 55130
60649 55130
14238 55130
56906 55130
75769 55130
48...

result:

ok AC

Test #64:

score: 0
Accepted
time: 41ms
memory: 13048kb

input:

100000
87758 1
87758 8566
8566 53230
53230 68035
45464 68035
43933 45464
7611 43933
7611 72530
72530 97898
97898 68231
2236 84498
71861 63091
76814 62314
24969 43571
98738 76356
71858 14301
12495 4041
49101 10912
83218 63817
60387 86854
59093 27607
35192 6135
76119 58917
15976 50822
5377 60508
39902...

output:

1 12837
87758 12837
8566 12837
53230 12837
68035 12837
45464 12837
43933 12837
7611 12837
72530 12837
97898 12837
84498 12837
71861 12837
76814 12837
43571 12837
76356 12837
14301 12837
4041 12837
49101 12837
63817 12837
86854 12837
59093 12837
35192 12837
76119 12837
50822 12837
5377 12837
39902 12...

result:

ok AC

Test #65:

score: 0
Accepted
time: 30ms
memory: 13412kb

input:

100000
49400 1
1 55311
78355 1
58471 1
25325 1
8216 1
19123 1
47311 1
1 87302
68137 1
1 98931
11168 1
1 42489
44803 1
25464 1
34243 1
63702 1
29572 1
14941 1
1 46103
1 54830
43707 1
57172 1
1 17538
75154 1
67663 1
1 6784
14487 1
45840 1
1 82849
1 77260
1 18850
1 7003
1 76083
16640 1
54748 1
46731 1
...

output:

49400 35021
55311 35021
78355 35021
58471 35021
25325 35021
8216 35021
19123 35021
47311 35021
87302 35021
68137 35021
98931 35021
11168 35021
42489 35021
44803 35021
25464 35021
34243 35021
63702 35021
29572 35021
14941 35021
46103 35021
54830 35021
43707 35021
57172 35021
17538 35021
75154 35021
6...

result:

ok AC

Test #66:

score: 0
Accepted
time: 42ms
memory: 13044kb

input:

100000
59098 1
88393 1
10097 1
1 27732
12542 1
1 74984
63414 1
1 68750
1 38087
65706 38087
46675 927
57918 60950
11844 60891
1200 51250
17750 31241
12177 66972
57772 85920
49826 92407
3739 18636
15328 31458
47706 69254
95722 85793
92734 12473
72338 65624
66312 27618
47426 68757
39713 32969
50029 618...

output:

59098 74702
88393 74702
10097 74702
27732 74702
12542 74702
74984 74702
63414 74702
68750 74702
1 74702
38087 74702
46675 74702
60950 74702
60891 74702
51250 74702
17750 74702
66972 74702
57772 74702
49826 74702
3739 74702
31458 74702
47706 74702
85793 74702
12473 74702
72338 74702
27618 74702
68757...

result:

ok AC

Test #67:

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

input:

5
2 1
1 3
4 1
5 4

output:

2 5
3 5
1 5
4 2

result:

ok AC

Test #68:

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

input:

5
4 1
3 1
5 1
5 2

output:

4 2
3 2
1 2
5 4

result:

ok AC

Test #69:

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

input:

5
5 1
3 1
1 2
2 4

output:

5 4
3 4
1 4
2 5

result:

ok AC