QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#751105#9743. 重心树lonelywolf#AC ✓44ms20564kbC++201.0kb2024-11-15 17:06:502024-11-15 17:06:50

Judging History

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

  • [2024-11-15 17:06:50]
  • 评测
  • 测评结果:AC
  • 用时:44ms
  • 内存:20564kb
  • [2024-11-15 17:06:50]
  • 提交

answer

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

#define int long long  

void solve() {
	int n;
	cin >> n;

	vector<int> c(n + 1);
	vector p(n + 1, vector<int>());
	for (int i = 1; i <= n; i++) {
		cin >> c[i];
		p[i].resize(c[i] + 1);
		for (int j = 1; j <= c[i]; j++) {
			cin >> p[i][j];
		}
	}

	vector<int> f(n + 1);
	for (int i = 1; i <= n; i++) {
		f[i] = i;
	}
	auto find = [&](int x) {
		while (x != f[x]) {
			x = f[x] = f[f[x]];
		}
		return x;
	};
	auto merge = [&](int x, int y) {
		x = find(x), y = find(y);
		if (x < y) {
			swap(x, y);
		}
		f[x] = y;
	};
	vector<int> fa(n + 1);
	for (int i = n; i >= 1; i--) {
		if (c[i] == 0) {
			continue;
		}
		for (int j = 1; j <= c[i]; j++) {
			fa[find(p[i][j])] = i;
			merge(p[i][j], i);
		}
	}

	for (int i = 2; i <= n; i++) {
		cout << i << " " << fa[i] << "\n";
	}
}

signed main() {  
    ios::sync_with_stdio(false);
    cin.tie(nullptr);  

    int t;
    cin >> t;
    while (t--) {
    	solve();
    }

    return 0;
}  
  

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2
4
2 3 4
1 3
0
0
3
1 3
1 3
0

output:

2 1
3 2
4 1
2 1
3 2

result:

ok Accepted (2 test cases)

Test #2:

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

input:

40000
3
2 2 3
0
0
2
1 2
0
4
2 4 3
1 4
0
0
5
1 3
2 5 4
1 5
0
0
4
3 2 3 4
0
0
0
2
1 2
0
2
1 2
0
5
1 2
3 3 4 5
0
0
0
2
1 2
0
2
1 2
0
5
4 2 3 4 5
0
0
0
0
4
1 2
2 3 4
0
0
5
2 5 4
1 5
1 4
0
0
2
1 2
0
5
1 2
3 3 4 5
0
0
0
5
2 2 3
0
2 4 5
0
0
5
2 5 4
1 5
1 4
0
0
5
2 2 4
2 3 5
0
0
0
4
1 3
1 4
1 4
0
4
2 4 3
1 ...

output:

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

result:

ok Accepted (40000 test cases)

Test #3:

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

input:

10000
5
2 3 4
1 5
1 5
0
0
4
2 3 4
1 3
0
0
7
1 2
3 4 7 6
1 4
0
1 7
0
0
2
1 2
0
2
1 2
0
8
1 3
1 4
3 4 5 6
2 7 8
0
0
0
0
4
2 2 4
0
1 4
0
4
1 2
2 3 4
0
0
4
1 2
2 3 4
0
0
2
1 2
0
7
3 3 4 6
1 7
1 7
0
1 6
0
0
4
2 4 3
1 4
0
0
3
2 2 3
0
0
6
2 5 4
1 6
1 4
0
1 6
0
3
2 2 3
0
0
5
3 2 5 4
0
1 5
0
0
7
2 4 6
1 5
1 ...

output:

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

result:

ok Accepted (10000 test cases)

Test #4:

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

input:

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

output:

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

result:

ok Accepted (10000 test cases)

Test #5:

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

input:

16
392
4 2 3 165 13
0
2 4 12
0
4 177 7 9 23
2 187 16
0
1 13
0
1 13
2 208 27
0
2 14 22
0
1 23
2 19 20
1 208
3 21 25 27
0
0
0
0
0
2 208 29
0
2 32 31
3 44 40 38
1 208
0
1 44
0
3 35 49 52
1 42
2 36 208
0
0
1 44
1 42
1 49
1 60
2 79 213
0
3 46 79 57
2 47 48
1 60
0
0
0
0
1 213
1 79
1 64
1 57
2 79 63
2 62 2...

output:

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

result:

ok Accepted (16 test cases)

Test #6:

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

input:

4
502
3 3 253 10
3 7 8 13
2 15 18
1 15
2 6 253
0
1 24
0
1 18
0
2 23 20
2 258 21
1 33
2 24 17
1 24
1 20
0
2 25 26
3 27 42 264
0
2 22 31
0
1 33
2 30 34
0
0
0
1 42
2 265 37
0
0
1 45
0
0
2 269 52
2 269 44
0
1 45
1 56
2 51 58
3 43 47 269
2 54 50
0
0
1 60
1 51
0
1 58
2 53 269
0
0
2 61 63
0
1 60
2 278 67
1...

output:

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

result:

ok Accepted (4 test cases)

Test #7:

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

input:

1
422
2 9 195
1 9
4 5 195 11 8
1 13
1 13
3 212 12 25
2 16 14
0
0
2 18 212
2 19 31
0
0
0
2 22 29
1 27
1 22
0
1 27
3 221 26 30
1 31
0
1 222
2 33 37
2 33 35
0
0
1 222
1 34
0
0
1 40
2 48 49
1 48
0
2 38 229
2 42 41
0
1 56
1 42
0
0
1 50
3 86 47 238
2 86 51
1 86
0
1 56
1 50
0
0
2 238 58
2 94 57
1 238
1 96
...

output:

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

result:

ok Accepted (1 test case)

Test #8:

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

input:

100
509
3 21 3 252
1 21
0
2 23 18
3 252 8 25
2 252 14
2 11 26
0
1 18
1 252
0
1 252
1 26
0
1 34
2 42 22
1 28
1 28
2 24 252
1 51
2 72 39
2 30 31
1 72
0
1 34
1 75
1 39
0
1 252
0
0
1 75
1 252
0
4 37 40 266 46
2 38 39
0
0
3 41 44 48
0
0
1 75
1 266
0
1 53
2 59 62
3 49 266 56
0
0
1 266
1 75
1 266
1 60
1 56...

output:

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

result:

ok Accepted (100 test cases)

Test #9:

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

input:

5
4174
3 9 15 2088
3 3 18 7
0
2 23 12
1 15
2 19 2088
0
1 19
1 23
2 11 2088
3 16 17 21
0
1 20
2 2088 38
0
0
0
2 28 27
1 20
0
0
2 2088 39
1 34
2 30 47
1 30
2 29 2088
0
1 34
0
0
1 39
1 47
1 2088
0
1 39
1 51
2 2088 44
2 42 51
2 46 49
2 55 2088
1 42
0
1 44
0
1 55
0
2 48 52
0
0
2 2088 58
2 59 53
1 63
0
2 ...

output:

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

result:

ok Accepted (5 test cases)

Test #10:

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

input:

4
32538
4 21 46 18 16255
2 14 22
1 46
1 17
1 18
2 8 50
2 16 11
1 16
1 16255
1 50
0
2 20 22
1 18
1 17
2 16272 33
0
0
2 23 27
1 50
0
2 32 28
2 30 36
0
1 16272
3 26 38 37
0
0
0
1 50
0
1 16272
1 36
2 42 53
1 39
1 50
0
1 39
3 51 44 48
0
1 50
1 16272
1 55
1 62
0
2 16299 78
1 59
1 16299
0
1 59
2 56 67
1 55...

output:

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

result:

ok Accepted (4 test cases)

Test #11:

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

input:

3
54304
3 7 27151 13
1 7
3 11 8 27158
2 6 11
1 22
2 9 12
0
0
0
1 27158
3 14 17 31
0
2 25 22
2 15 23
0
1 25
0
1 31
1 27158
1 26
2 36 27158
3 27 28 34
0
1 40
1 26
0
0
0
1 36
2 27158 48
1 40
1 34
2 41 27158
0
1 41
0
5 27175 42 45 46 73
1 48
1 27175
0
0
0
2 52 58
1 27175
0
0
2 50 73
2 49 57
0
0
3 54 56 ...

output:

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

result:

ok Accepted (3 test cases)

Test #12:

score: 0
Accepted
time: 19ms
memory: 8344kb

input:

2
64362
6 2 13 32175 17 6 18
0
3 15 11 23
2 32175 14
1 17
0
1 15
1 11
1 18
2 32175 20
0
2 22 21
1 28
0
0
1 32175
2 22 24
0
1 32175
0
0
2 27 32
2 25 33
0
0
2 31 32175
0
1 33
2 36 40
1 36
1 36
0
0
3 32175 48 42
1 32175
2 37 46
0
1 40
2 56 45
0
1 56
0
3 32182 80 60
3 32182 52 53
0
0
1 80
1 57
2 32192 7...

output:

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

result:

ok Accepted (2 test cases)

Test #13:

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

input:

1
194798
3 2 3 97357
0
0
3 6 8 97357
1 6
0
2 16 32
1 24
3 97357 14 19
2 97357 13
2 97357 20
1 32
0
0
2 97357 29
2 28 26
1 97357
2 97357 27
0
0
1 29
1 37
1 97357
1 28
2 35 97357
0
0
0
0
1 35
4 33 34 97357 45
1 37
0
0
0
2 38 97357
0
0
3 97357 48 67
1 45
1 50
1 97357
2 97361 47
3 106 97382 59
1 50
1 48...

output:

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

result:

ok Accepted (1 test case)

Test #14:

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

input:

10000
8
2 2 5
3 8 6 7
1 5
1 8
0
0
0
0
8
4 3 4 8 7
1 5
1 5
0
0
1 8
0
0
4
2 2 4
0
1 4
0
3
2 2 3
0
0
2
1 2
0
12
1 4
4 3 8 10 6
0
2 7 11
1 10
0
0
2 9 12
0
0
1 12
0
6
2 3 5
2 6 4
1 6
0
0
0
4
1 3
1 4
1 4
0
7
2 3 7
1 5
2 4 6
0
1 6
0
0
14
4 2 13 5 7
2 4 6
1 13
2 8 14
2 9 11
2 10 12
0
0
0
0
0
0
0
0
4
2 4 3
1...

output:

2 1
3 1
4 2
5 3
6 2
7 2
8 4
2 1
3 2
4 1
5 3
6 1
7 1
8 6
2 1
3 1
4 3
2 1
3 1
2 1
2 1
3 2
4 2
5 2
6 2
7 4
8 4
9 8
10 5
11 8
12 11
2 1
3 2
4 2
5 1
6 3
2 1
3 2
4 3
2 1
3 2
4 3
5 3
6 5
7 1
2 1
3 1
4 2
5 1
6 2
7 1
8 4
9 5
10 6
11 5
12 6
13 3
14 4
2 1
3 1
4 2
2 1
3 2
4 1
2 1
3 2
4 1
5 4
6 2
7 5
8 1
9 2
10 ...

result:

ok Accepted (10000 test cases)

Test #15:

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

input:

10000
14
2 2 10
4 6 4 5 12
1 6
2 7 9
2 11 13
0
0
1 14
0
1 14
0
0
0
0
11
4 4 5 6 11
2 7 10
1 5
2 8 9
0
0
1 8
0
0
0
0
9
4 3 4 6 7
1 8
2 5 9
0
0
0
0
1 9
0
16
2 8 7
2 12 8
1 12
1 8
1 7
1 13
0
4 9 10 15 16
0
0
1 15
1 13
0
1 16
0
0
10
3 4 3 7
2 10 5
0
1 10
0
1 7
2 8 9
0
0
0
5
3 5 3 4
1 5
0
0
0
7
2 3 5
2 3...

output:

2 1
3 2
4 2
5 2
6 3
7 4
8 1
9 4
10 8
11 5
12 2
13 5
14 10
2 1
3 1
4 2
5 3
6 1
7 4
8 7
9 4
10 2
11 1
2 1
3 2
4 1
5 3
6 1
7 1
8 3
9 8
2 1
3 2
4 2
5 1
6 3
7 5
8 4
9 8
10 8
11 8
12 6
13 12
14 8
15 11
16 14
2 1
3 1
4 2
5 2
6 1
7 6
8 7
9 7
10 4
2 1
3 1
4 1
5 2
2 1
3 2
4 3
5 1
6 2
7 3
2 1
3 1
4 3
5 4
6 1
7...

result:

ok Accepted (10000 test cases)

Test #16:

score: 0
Accepted
time: 19ms
memory: 3512kb

input:

10000
17
2 2 12
4 14 6 11 10
2 7 12
1 14
1 6
0
0
2 15 13
1 12
0
1 15
2 16 17
0
0
0
0
0
9
3 5 4 9
1 5
1 4
0
2 7 8
1 9
0
0
0
5
2 3 5
1 4
1 4
0
0
18
3 4 3 10
2 9 16
0
2 14 12
3 8 15 11
1 18
1 14
0
1 13
1 17
0
1 13
0
0
1 17
1 18
0
0
2
1 2
0
14
3 3 13 7
2 6 11
1 10
1 13
2 8 14
1 10
1 12
1 12
1 14
0
0
0
0...

output:

2 1
3 1
4 2
5 2
6 5
7 3
8 2
9 3
10 2
11 8
12 9
13 8
14 4
15 11
16 12
17 12
2 1
3 1
4 3
5 2
6 1
7 5
8 5
9 6
2 1
3 2
4 3
5 1
2 1
3 1
4 2
5 1
6 2
7 4
8 5
9 4
10 5
11 5
12 9
13 12
14 7
15 10
16 6
17 15
18 16
2 1
2 1
3 2
4 1
5 1
6 3
7 5
8 7
9 5
10 6
11 2
12 8
13 4
14 9
2 1
3 2
4 2
5 1
6 3
7 6
8 2
9 5
10 ...

result:

ok Accepted (10000 test cases)

Test #17:

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

input:

10000
12
3 3 6 11
2 9 7
1 9
1 12
1 7
1 12
0
1 10
1 10
0
0
0
9
4 7 5 6 9
1 7
1 8
1 5
0
0
1 8
0
0
16
3 5 3 6
3 4 7 12
0
0
2 7 11
0
3 9 15 13
1 11
0
1 15
0
2 14 16
0
0
0
0
13
1 3
3 4 8 10
4 6 7 9 12
2 5 6
0
2 11 13
0
0
0
0
0
0
0
4
2 4 3
1 4
0
0
8
2 5 3
2 6 7
0
1 6
1 8
1 8
0
0
20
2 7 6
3 4 10 11
2 13 8
...

output:

2 1
3 2
4 1
5 2
6 4
7 5
8 3
9 8
10 9
11 1
12 6
2 1
3 2
4 1
5 4
6 1
7 3
8 7
9 1
2 1
3 1
4 2
5 2
6 1
7 5
8 5
9 7
10 7
11 8
12 2
13 7
14 12
15 10
16 12
2 1
3 2
4 3
5 4
6 4
7 3
8 2
9 3
10 2
11 6
12 3
13 6
2 1
3 1
4 2
2 1
3 1
4 2
5 4
6 5
7 2
8 6
2 1
3 1
4 2
5 4
6 3
7 2
8 3
9 7
10 9
11 2
12 10
13 6
14 4
1...

result:

ok Accepted (10000 test cases)

Test #18:

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

input:

100000
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2...

output:

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

result:

ok Accepted (100000 test cases)

Test #19:

score: 0
Accepted
time: 44ms
memory: 19164kb

input:

1
200000
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 6...

output:

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

result:

ok Accepted (1 test case)

Test #20:

score: 0
Accepted
time: 34ms
memory: 20564kb

input:

1
200000
5703 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 1374 1375 1440 1486 1487 1488 1489 1845 1846 1847 1848 1849 1850 1851 1860 1861 1862 1863 1864 1865 1866 1867 1868 1888 1889 3321 3322 3323 3324 3325 3326 3327 3328 3329 3330 3446 ...

output:

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

result:

ok Accepted (1 test case)

Test #21:

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

input:

1
200000
11 39 63012 63019 63148 63219 63220 63262 63263 130152 198563 199731
9 3 4 39 60342 60876 60977 62603 62911 62944
0
5 5 7 23 25 36
0
3 8 19 22
4 8 15 16 18
4 9 10 12 14
0
0
1 13
1 13
0
0
0
0
1 18
0
2 20 21
0
0
0
0
2 27 31
2 26 29
0
2 28 30
0
1 30
0
3 32 33 35
0
0
1 35
0
2 37 38
0
0
15 41 42...

output:

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

result:

ok Accepted (1 test case)

Test #22:

score: 0
Accepted
time: 44ms
memory: 11068kb

input:

2
100000
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 1...

output:

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

result:

ok Accepted (2 test cases)

Test #23:

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

input:

2
100000
2810 2 3 4 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 951 952 953 1008 1009 1010 1019 1020 1021 1046 1047 1048 1049 1050 1581 1582 1583 1584 1585 1586 1587 1588 1589 1651 1652 1653 1654 1655 1656 1657 1658 1659 1660 1661 1662 1680 1693 1694 1711 1712 1713 1732 1733 1951 1952 2040 20...

output:

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

result:

ok Accepted (2 test cases)

Extra Test:

score: 0
Extra Test Passed