QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#418808#2830. Data StructuredieselhuangAC ✓101ms13540kbC++142.7kb2024-05-23 15:52:562024-05-23 15:52:57

Judging History

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

  • [2024-05-23 15:52:57]
  • 评测
  • 测评结果:AC
  • 用时:101ms
  • 内存:13540kb
  • [2024-05-23 15:52:56]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
int n, m, X, Y, tp, cnt, k[200010], a[200010][2], pos[200010][2], stk[400010], ans[300010][2];
bool bk[200010];
void chg(int x, int y){
	cnt++; ans[cnt][0] = x; ans[cnt][1] = y;
	if(X == y){ X = Y; Y = 0; }
	else if(Y == y) Y = 0;
	int i = a[x][--k[x]];
	if(pos[i][0] == x) pos[i][0] = y;
	else pos[i][1] = y;
	a[y][k[y]++] = i;
	if(k[x] > 0) stk[++tp] = a[x][k[x] - 1];
	else if(X == 0) X = x;
	else if(Y == 0) Y = x;
}
void upd(){
	int i, x, y;
	while(tp > 0){
		i = stk[tp--]; x = pos[i][0]; y = pos[i][1];
		if(x == y || i != a[x][k[x] - 1] || i != a[y][k[y] - 1]) continue;
		if(k[x] == 1) chg(y, x);
		else if(k[y] == 1) chg(x, y);
	}
}
void dfs1(int u, int fa){
	int x = pos[u][0] + pos[u][1] - fa;
	bool fl = (a[fa][k[fa] - 1] == u && a[x][k[x] - 1] == u);
	if(k[x] > 1) dfs1(a[x][0] + a[x][1] - u, x);
	if(fl){
		int tmp = X;
		chg(fa, tmp); chg(x, tmp); upd();
	}
}
void dfs2(int u, int fa, int rt, int &p){
	int x = pos[u][0] + pos[u][1] - fa;
	if(a[fa][1] == u && a[x][1] == u){
		if(p == 0) p = u;
		else p = -1;
	}
	if(x != rt) dfs2(a[x][0] + a[x][1] - u, x, rt, p);
}
void dfs3(int u, int fa, int rt){
	bk[fa] = true;
	int x = pos[u][0] + pos[u][1] - fa;
	if(x != rt) dfs3(a[x][0] + a[x][1] - u, x, rt);
}
void dfs4(int u, int fa, int rt){
	int x = pos[u][0] + pos[u][1] - fa;
	bool fl = (a[fa][1] == u && a[x][1] == u);
	if(x != rt) dfs4(a[x][0] + a[x][1] - u, x, rt);
	if(fl){
		int tmp = X;
		chg(fa, tmp); chg(x, tmp); upd();
	}
}
void solve(){
	X = 0; Y = 0; tp = 0; cnt = 0;
	int i, j, tmp;
	for(i = 1; i <= n; i++) pos[i][0] = 0;
	for(i = 1; i <= m; i++){
		scanf("%d", &k[i]);
		for(j = 0; j < k[i]; j++){
			scanf("%d", &a[i][j]);
			if(pos[a[i][j]][0] == 0) pos[a[i][j]][0] = i;
			else pos[a[i][j]][1] = i;
		}
		if(k[i] > 0) stk[++tp] = a[i][k[i] - 1];
		else if(X == 0) X = i;
		else if(Y == 0) Y = i;
		bk[i] = false;
	}
	upd();
	if(X != 0){
		for(i = 1; i <= m; i++){
			if(k[i] == 1) dfs1(a[i][k[i] - 1], i);
		}
		for(i = 1; i <= m; i++){
			if(k[i] == 2 && !bk[i] && a[i][0] != a[i][1]){
				j = 0; dfs2(a[i][0], i, i, j);
				if(j == 0){
					chg(i, X); upd();
				}else if(j > 0){
					tmp = X; chg(pos[j][0], tmp); chg(pos[j][1], tmp); upd();
				}else dfs3(a[i][0], i, i);
			}
		}
		if(Y != 0){
			for(i = 1; i <= m; i++){
				if(k[i] == 2 && bk[i] && a[i][0] != a[i][1]){
					dfs4(a[i][0], i, i);
				}
			}
		}
	}
	for(i = 1; i <= n; i++){
		if(pos[i][0] != pos[i][1]){ printf("-1\n"); return; }
	}
	printf("%d\n", cnt);
	for(i = 1; i <= cnt; i++) printf("%d %d\n", ans[i][0], ans[i][1]);
}
int main()
{
	while(~scanf("%d%d", &n, &m)){
		solve();
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

3
1 3
2 3
2 1
0
-1

result:

ok 3 cases passed. max #moves/#balls = 1.500000000

Test #2:

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

input:

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

output:

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

result:

ok 6 cases passed. max #moves/#balls = 1.000000000

Test #3:

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

input:

2 4
1 1
1 2
1 2
1 1
2 5
1 1
1 2
0
1 1
1 2
2 6
0
1 1
0
1 1
1 2
1 2
2 4
1 2
1 1
1 1
1 2
2 5
1 1
0
1 2
1 2
1 1
2 6
1 2
0
1 1
0
1 1
1 2
2 4
1 1
1 2
1 2
1 1
2 5
0
1 2
1 1
1 1
1 2
2 6
1 1
0
1 2
1 2
0
1 1
2 3
2 2 1
1 1
1 2
2 4
2 2 1
1 1
0
1 2
2 5
1 1
0
1 2
2 1 2
0
2 3
1 2
2 1 2
1 1
2 4
1 1
2 2 1
1 2
0
2 5
...

output:

2
4 1
3 2
2
5 2
4 1
2
6 5
4 2
2
4 1
3 2
2
5 1
4 3
2
6 1
5 3
2
4 1
3 2
2
5 2
4 3
2
6 1
4 3
2
1 2
3 1
2
1 2
4 1
2
4 3
4 1
2
2 1
3 2
2
2 1
3 2
2
1 3
4 1
-1
3
2 1
3 1
3 2
3
2 1
4 1
4 2
-1
3
1 3
2 1
2 3
3
1 3
2 1
2 3
1
3 2
1
4 3
1
4 1
0
0
0

result:

ok 27 cases passed. max #moves/#balls = 1.500000000

Test #4:

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

input:

3 6
1 1
1 2
1 2
1 3
1 3
1 1
3 7
1 3
0
1 2
1 2
1 1
1 1
1 3
3 8
0
1 3
1 2
0
1 1
1 1
1 2
1 3
3 6
1 3
1 3
1 2
1 1
1 1
1 2
3 7
1 1
1 3
1 1
1 2
1 2
1 3
0
3 8
1 1
1 2
0
1 3
1 2
0
1 3
1 1
3 6
1 3
1 1
1 2
1 3
1 2
1 1
3 7
1 1
1 2
0
1 1
1 3
1 3
1 2
3 8
1 2
1 1
1 3
1 2
0
1 3
0
1 1
3 6
1 2
1 2
1 3
1 1
1 1
1 3
3 ...

output:

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

result:

ok 180 cases passed. max #moves/#balls = 1.333333333

Test #5:

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

input:

4 8
1 3
1 3
1 4
1 1
1 2
1 1
1 4
1 2
4 9
1 3
0
1 2
1 1
1 4
1 1
1 4
1 2
1 3
4 10
1 1
1 3
1 3
1 2
1 2
0
1 1
1 4
1 4
0
4 8
1 4
1 3
1 2
1 2
1 1
1 4
1 1
1 3
4 9
1 4
1 3
1 1
1 3
1 4
1 2
1 1
1 2
0
4 10
1 4
1 1
1 2
1 3
0
0
1 2
1 1
1 3
1 4
4 8
1 2
1 4
1 3
1 4
1 2
1 3
1 1
1 1
4 9
1 1
1 4
1 3
1 2
1 3
1 2
0
1 4
...

output:

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

result:

ok 1575 cases passed. max #moves/#balls = 1.500000000

Test #6:

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

input:

5 10
1 1
1 4
1 2
1 4
1 5
1 2
1 3
1 5
1 1
1 3
5 11
1 1
1 3
1 1
1 2
1 5
1 2
0
1 5
1 4
1 3
1 4
5 12
1 2
0
1 1
1 5
1 2
1 4
1 3
1 4
0
1 5
1 3
1 1
5 10
1 3
1 5
1 1
1 1
1 2
1 4
1 4
1 5
1 2
1 3
5 11
1 3
1 5
1 2
1 2
1 4
1 3
1 1
1 1
0
1 4
1 5
5 12
1 3
1 4
1 2
0
1 5
1 1
1 2
1 1
1 4
1 5
0
1 3
5 10
1 4
1 5
1 3
1...

output:

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

result:

ok 17010 cases passed. max #moves/#balls = 1.400000000

Test #7:

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

input:

6 11
1 5
1 6
1 2
1 4
1 1
1 5
1 4
1 3
1 6
2 2 3
1 1
6 9
1 6
2 1 1
2 4 4
1 2
2 6 2
0
2 5 3
0
2 5 3
6 6
2 4 4
2 5 6
2 3 6
2 2 2
2 3 5
2 1 1
6 8
2 2 1
2 3 4
1 6
2 1 2
2 3 5
0
1 6
2 4 5
6 9
1 6
1 4
1 3
1 5
2 3 1
2 4 2
2 2 1
1 6
1 5
6 7
1 4
2 2 3
2 1 6
2 1 4
2 6 2
2 5 5
1 3
6 8
1 2
2 3 5
1 1
2 4 4
0
2 5 1...

output:

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

result:

ok 14285 cases passed. max #moves/#balls = 1.500000000

Test #8:

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

input:

7 10
2 4 3
1 1
2 2 2
2 4 3
2 7 7
2 6 6
2 5 5
0
1 1
0
7 12
1 2
1 6
1 6
1 5
2 4 1
1 1
2 4 3
1 7
1 5
1 3
1 2
1 7
7 15
1 4
1 6
1 2
1 4
1 6
1 5
1 7
1 1
1 3
0
1 7
1 5
1 1
1 3
1 2
7 7
2 7 3
2 2 3
2 5 7
2 1 1
2 6 6
2 2 5
2 4 4
7 12
2 3 2
1 7
2 6 3
1 4
1 2
1 5
1 1
1 4
1 5
1 1
1 6
1 7
7 14
2 3 5
0
1 2
1 6
1 4...

output:

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

result:

ok 12500 cases passed. max #moves/#balls = 1.428571429

Test #9:

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

input:

8 16
1 2
0
1 5
1 8
1 1
1 5
2 4 4
1 8
1 6
1 1
1 2
0
2 7 7
1 3
1 6
1 3
8 13
1 8
1 4
1 2
1 6
2 1 3
2 1 3
1 7
1 2
1 5
1 6
1 8
2 4 5
1 7
8 9
2 1 3
2 4 5
2 7 2
2 7 8
2 4 8
2 1 6
2 5 2
2 6 3
0
8 17
1 1
1 4
1 3
1 7
1 2
1 2
1 7
1 5
1 3
1 4
1 6
1 8
1 5
1 6
1 8
1 1
0
8 15
1 6
1 4
0
1 5
1 7
1 3
1 2
1 8
1 6
1 7
...

output:

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

result:

ok 11111 cases passed. max #moves/#balls = 1.500000000

Test #10:

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

input:

9 13
1 2
2 4 5
2 5 4
2 2 9
1 8
1 3
1 1
1 3
1 1
2 7 6
1 9
1 8
2 7 6
9 13
1 4
2 5 6
2 7 5
2 9 3
1 4
2 9 7
0
2 8 6
2 1 3
0
1 2
1 2
2 8 1
9 18
1 4
1 7
1 7
1 9
1 8
1 8
1 2
1 3
1 6
1 2
1 1
1 3
1 5
1 1
1 6
1 5
1 4
1 9
9 13
0
2 6 7
2 2 2
1 3
2 6 8
2 9 1
2 1 4
1 9
2 8 7
0
1 4
1 3
2 5 5
9 17
1 9
2 1 3
1 2
1 5...

output:

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

result:

ok 10000 cases passed. max #moves/#balls = 1.444444444

Test #11:

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

input:

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

output:

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

result:

ok 9090 cases passed. max #moves/#balls = 1.500000000

Test #12:

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

input:

11 15
2 11 11
2 3 3
1 2
0
2 8 5
1 2
2 6 4
2 4 5
1 1
1 1
1 9
1 10
2 8 6
2 7 7
2 9 10
11 17
2 4 8
1 11
2 6 7
1 9
1 9
1 5
1 2
1 2
1 5
1 10
1 3
1 1
1 11
2 10 8
1 1
2 3 7
2 4 6
11 21
1 10
1 6
1 3
1 9
1 8
1 1
1 5
1 10
1 5
1 4
1 8
1 9
1 11
1 6
1 11
1 7
1 1
1 4
2 2 2
1 7
1 3
11 15
1 5
1 1
1 2
2 3 3
2 10 7
0...

output:

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

result:

ok 8333 cases passed. max #moves/#balls = 1.363636364

Test #13:

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

input:

12 25
1 9
1 10
1 4
1 7
1 5
1 3
1 6
1 1
1 12
1 3
1 2
1 9
1 11
1 2
0
1 10
1 7
1 12
1 11
1 4
1 6
1 5
1 1
1 8
1 8
12 19
1 2
1 12
2 8 8
2 1 3
0
2 3 4
1 5
2 11 11
2 1 5
2 9 6
1 12
1 7
1 7
2 6 9
1 2
1 4
1 10
1 10
0
12 14
2 2 4
2 8 8
2 1 3
2 9 9
2 6 12
2 6 1
0
2 10 10
2 5 5
2 3 12
0
2 4 7
2 7 2
2 11 11
12 1...

output:

12
25 24
23 8
22 5
21 7
20 3
19 13
18 9
17 4
16 2
14 11
12 1
10 6
11
18 17
6 16
4 6
15 1
13 12
11 2
9 7
9 4
10 5
14 10
14 5
9
1 7
13 1
12 13
12 7
5 11
10 11
3 10
6 3
6 5
10
14 5
8 5
3 8
1 3
7 13
12 13
4 12
6 4
14 6
7 1
12
25 16
24 11
22 8
21 12
20 4
19 5
18 15
17 9
14 7
13 3
10 1
6 2
11
12 2
5 4
8 9...

result:

ok 7692 cases passed. max #moves/#balls = 1.416666667

Test #14:

score: 0
Accepted
time: 36ms
memory: 10088kb

input:

13 15
2 8 8
2 6 6
2 1 1
2 3 3
2 11 11
2 2 5
2 5 13
1 4
1 12
2 2 13
1 12
2 10 10
1 4
2 9 9
2 7 7
13 21
2 11 11
1 9
1 2
1 9
1 13
1 1
1 13
1 5
2 12 8
2 7 7
1 5
1 6
1 6
2 4 3
1 1
0
2 10 10
1 2
2 4 3
0
2 8 12
13 24
1 8
1 7
1 6
1 3
1 5
1 9
1 2
1 13
1 2
1 12
2 10 10
1 3
1 1
1 8
1 4
1 12
1 6
1 5
1 7
1 4
2 1...

output:

6
13 8
11 9
7 13
10 13
6 7
10 6
12
18 3
15 6
13 12
11 8
7 5
4 2
9 16
21 9
21 16
14 20
19 20
19 14
11
24 6
23 13
22 8
20 15
19 2
18 5
17 3
16 10
14 1
12 4
9 7
12
20 13
17 3
16 4
15 8
14 2
11 1
10 6
9 7
10 9
5 20
19 20
19 5
12
27 1
26 12
25 2
23 5
22 21
20 4
19 11
18 9
17 7
16 10
14 8
6 3
13
26 23
25 ...

result:

ok 7142 cases passed. max #moves/#balls = 1.384615385

Test #15:

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

input:

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

output:

13
24 21
8 24
10 8
13 10
23 19
22 14
20 12
18 4
17 3
11 1
9 5
13 9
7 2
13
27 24
26 9
25 1
23 12
22 17
20 16
19 8
18 7
15 11
14 6
13 2
10 5
4 3
12
22 19
21 4
20 14
17 1
15 3
8 13
11 8
6 5
2 18
7 18
10 2
10 7
13
25 16
21 6
20 8
19 2
18 11
17 14
15 4
12 7
10 9
3 1
13 24
23 24
23 13
14
29 22
28 3
27 1
2...

result:

ok 6666 cases passed. max #moves/#balls = 1.357142857

Test #16:

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

input:

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

output:

14
21 4
17 11
10 15
9 10
6 5
2 3
14 2
13 1
12 1
22 12
13 9
8 7
19 8
19 7
13
24 15
13 24
19 13
23 18
22 6
20 1
17 2
14 17
3 14
19 3
16 10
12 11
8 4
12
24 23
22 6
8 18
8 5
16 15
14 9
13 10
12 7
3 2
17 1
19 1
19 17
15
17 6
7 3
13 3
13 7
14 17
2 17
12 14
15 13
11 13
12 11
16 12
10 12
15 10
5 16
5 2
16
2...

result:

ok 6250 cases passed. max #moves/#balls = 1.400000000

Test #17:

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

input:

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

output:

14
20 8
15 6
7 5
9 7
4 2
22 3
21 3
21 14
22 1
18 16
23 16
23 19
12 18
12 9
17
29 11
28 18
27 24
26 21
25 6
23 9
23 17
22 4
19 14
15 12
13 7
13 2
10 5
8 3
16 1
20 16
20 1
16
28 6
27 16
26 19
25 7
24 3
24 15
23 12
22 9
21 10
20 13
17 4
14 2
11 1
5 28
18 28
18 5
15
23 7
21 15
19 10
18 12
14 8
13 1
6 3
...

result:

ok 5882 cases passed. max #moves/#balls = 1.375000000

Test #18:

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

input:

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

output:

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

result:

ok 5555 cases passed. max #moves/#balls = 1.352941176

Test #19:

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

input:

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

output:

19
9 5
11 5
10 9
18 10
1 18
11 1
2 11
6 11
19 6
19 2
3 19
14 3
14 19
7 14
12 7
12 14
13 12
16 12
16 13
21
25 8
23 17
21 10
20 3
18 9
16 15
14 4
6 5
19 25
22 25
13 22
1 13
19 1
2 23
7 2
7 23
11 19
24 19
26 24
12 11
26 12
14
23 16
13 6
12 10
11 18
15 18
4 15
20 4
2 11
19 2
7 19
20 7
14 21
17 14
17 21
...

result:

ok 5263 cases passed. max #moves/#balls = 1.388888889

Test #20:

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

input:

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

output:

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

result:

ok 5000 cases passed. max #moves/#balls = 1.368421053

Test #21:

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

input:

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

output:

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

result:

ok 4761 cases passed. max #moves/#balls = 1.300000000

Test #22:

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

input:

70 79
2 13 14
2 49 46
1 43
2 27 27
2 5 5
2 63 50
2 63 15
2 61 25
2 17 39
2 44 26
2 15 45
2 65 2
2 64 6
2 2 28
2 55 60
2 13 68
1 40
2 30 30
1 62
2 41 60
2 16 25
1 69
1 62
2 28 23
2 46 49
2 26 57
1 35
2 66 66
2 10 69
2 33 55
1 10
2 54 9
1 32
2 11 12
1 40
1 7
1 29
2 33 54
2 12 11
2 22 1
1 29
2 6 64
2 2...

output:

79
75 33
62 27
50 44
47 3
45 36
41 37
35 17
29 22
31 29
23 19
1 75
65 75
16 65
16 1
2 62
25 2
25 62
12 16
71 12
24 71
14 24
14 16
13 25
42 13
42 25
34 14
39 34
39 14
46 42
66 46
66 42
53 39
57 53
70 57
70 39
58 66
77 66
77 58
73 70
6 70
11 77
74 77
76 74
51 76
48 51
56 48
73 56
7 11
7 6
21 73
8 73
6...

result:

ok 1000 cases passed. max #moves/#balls = 1.500000000

Test #23:

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

input:

89 125
2 6 86
1 11
1 43
1 77
1 27
2 72 88
1 52
2 26 75
1 77
2 89 86
1 60
1 18
2 20 20
1 25
2 57 75
1 3
1 55
2 38 19
2 76 2
2 22 24
1 3
2 61 61
2 39 59
2 42 74
1 56
2 71 71
1 68
2 79 87
2 81 67
1 25
2 66 21
1 37
1 70
2 40 83
1 60
1 48
1 52
2 22 24
2 62 62
1 84
2 41 23
1 69
2 32 26
1 36
1 15
2 88 72
1...

output:

88
123 17
122 27
119 83
118 82
117 32
116 73
115 33
114 45
113 110
112 56
109 95
108 12
107 57
63 106
105 2
98 61
96 59
94 36
93 54
92 48
91 85
90 25
88 79
87 44
78 51
76 62
75 3
64 40
52 42
47 5
37 7
35 11
30 14
21 16
9 4
19 81
67 81
34 67
77 34
70 19
70 63
6 123
46 6
46 123
8 77
15 77
89 15
43 8
8...

result:

ok 100 cases passed. max #moves/#balls = 1.169811321

Test #24:

score: 0
Accepted
time: 86ms
memory: 12840kb

input:

199990 199994
2 112787 58235
2 74630 28941
2 167642 28933
2 133872 119903
2 134119 187247
2 12074 126849
2 172463 191232
2 69306 129651
2 85342 121061
2 31874 148765
2 6567 39825
2 70847 178127
2 161417 173942
2 60884 49005
2 10700 112396
2 134185 131889
2 62930 176558
2 153356 48329
2 88968 136672
...

output:

249866
45681 123950
29499 45681
52624 103430
47930 39403
33532 199993
149868 199993
55718 149868
174021 55718
40140 199994
154492 199994
98071 154492
98071 33532
3409 40140
127577 3409
183763 174021
146781 174021
146781 127577
177569 183763
39870 177569
128051 39870
40416 128051
47653 40416
24457 47...

result:

ok 1 cases passed. max #moves/#balls = 1.249392470

Test #25:

score: 0
Accepted
time: 80ms
memory: 11980kb

input:

199900 199939
2 159852 65847
2 26090 50275
2 87513 124862
2 86896 171149
2 108960 21092
2 60944 176432
2 64408 168417
2 110938 48609
2 30886 178149
2 180183 52005
2 185615 173446
2 91034 36919
2 121714 75547
2 97679 89549
2 161524 190571
2 129781 26065
2 726 162459
2 28052 166745
2 193665 65435
2 45...

output:

249613
197876 195998
106581 195508
61879 106581
193688 130694
193462 112079
79103 193462
142645 79103
137649 142645
141132 188272
186238 148645
110210 186238
144467 110210
172814 144467
184780 156194
36392 181613
11595 36392
111161 180271
177189 95960
83100 170999
146264 83100
109914 146264
73827 17...

result:

ok 1 cases passed. max #moves/#balls = 1.248689345

Test #26:

score: 0
Accepted
time: 85ms
memory: 11900kb

input:

199000 199158
2 87128 180318
2 51427 22755
2 151883 144846
2 86404 42933
2 86031 56171
2 97601 190366
2 100929 91717
2 10606 53797
2 151688 90226
2 65599 83910
2 159670 153323
2 98395 126956
2 104190 188119
2 134860 5110
2 82527 59574
2 185228 58544
2 131591 9348
2 88390 99580
2 79913 120984
2 12854...

output:

248620
177708 198873
2295 177708
190108 2295
28323 198599
162531 28323
130923 197526
108690 130923
194040 96305
186424 193560
193496 103084
108644 192770
52653 108644
191949 77512
191723 110773
64324 191723
186152 40397
184853 35084
184348 40546
55779 184348
9660 55779
39136 9660
57803 183718
159981...

result:

ok 1 cases passed. max #moves/#balls = 1.249346734

Test #27:

score: 0
Accepted
time: 73ms
memory: 11936kb

input:

190000 195490
2 57925 137657
2 115225 31941
2 113825 126389
2 86640 44883
2 54487 34585
2 118366 61471
2 120619 96922
1 140665
2 42131 138488
2 115971 83797
2 79814 139047
2 182772 4122
2 134485 135722
2 83056 53620
2 4840 71513
2 58767 175090
2 55378 47553
2 158331 65564
2 2231 167672
2 45248 44008...

output:

234894
57287 195481
50352 57287
113863 195478
195463 37750
195422 112777
43842 195416
52331 195344
123184 52331
84121 123184
157137 195326
40458 195298
195288 122237
195273 45436
195252 83076
50768 195245
127165 50768
5090 195241
7113 5090
195233 176847
154240 195153
195151 63028
74767 195134
130367...

result:

ok 1 cases passed. max #moves/#balls = 1.236284211

Test #28:

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

input:

100000 150784
1 11363
2 48695 10015
1 45261
0
0
2 59469 34868
2 37754 54971
2 1159 2258
2 36656 7427
1 86418
0
2 58664 20429
1 53392
1 61881
2 17499 14399
1 31182
1 7141
0
2 58765 17577
1 21750
2 55759 24096
0
0
2 68221 45178
1 34307
1 952
0
1 37862
1 31349
2 79909 53730
2 61993 40470
0
1 8272
2 824...

output:

111036
142726 150781
5647 142726
115157 5647
3218 115157
150780 113716
29540 150779
25421 150773
98471 25421
150770 140176
150767 53323
5969 150766
150765 127582
150765 45925
150758 112446
67697 150755
121922 67697
127998 150753
127998 238
150751 71134
81770 150750
81770 60056
150745 39859
150743 14...

result:

ok 1 cases passed. max #moves/#balls = 1.110360000

Test #29:

score: 0
Accepted
time: 101ms
memory: 13540kb

input:

199998 200000
2 197320 165241
2 136684 67821
2 38136 196111
2 36675 168634
2 193814 85383
2 188893 178378
2 107377 34791
2 77322 157440
2 51337 91683
2 141729 123337
2 88834 166216
2 172041 99918
2 81678 190214
2 145905 79139
2 184733 143722
2 20662 175460
2 73374 152647
2 111949 12058
2 7347 64349
...

output:

250095
53982 199999
138669 199999
35536 138669
1 35536
19591 1
156892 200000
26080 200000
22878 26080
53982 22878
139880 156892
5236 139880
141273 53982
8108 53982
45569 8108
45569 5236
154646 45569
37924 45569
147006 37924
147006 141273
28742 154646
143141 147006
94441 147006
94441 28742
29668 1431...

result:

ok 1 cases passed. max #moves/#balls = 1.250487505