QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#419182#2830. Data Structurejinqihao2023AC ✓157ms63156kbC++143.5kb2024-05-23 18:31:332024-05-23 18:31:35

Judging History

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

  • [2024-05-23 18:31:35]
  • 评测
  • 测评结果:AC
  • 用时:157ms
  • 内存:63156kb
  • [2024-05-23 18:31:33]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,m,ax[N],ay[N],d[N],ned[N],l1[N];
int prt[N];
vector<int>bel[N],tr[N];
int gf(int x){if(x==prt[x])return x;return prt[x]=gf(prt[x]);}
void merge(int x,int y){x=gf(x),y=gf(y);if(x!=y)prt[x]=y;}
struct abc{int a,b;};
struct abcd{int to,a;};
vector<abc>op[N],ans;
vector<abcd>son[N],son1[N];
int st[N],top,pos[N],ad[N];
vector<int>all,oth[N];
bool cmp(int a,int b){return ned[a]<ned[b];}
int temp[4];
struct ab
{
	int pos,cd,tag;
	bool operator < (const ab &a) const
	{
		if(cd!=a.cd)return cd>a.cd;
		return tag>a.tag;
	}
};
bool vis[N];
int tot;
void dfs(int x)
{
	vis[x]=1,pos[x]=++tot;bool fl=0;
	for(auto y:son[x])if(!vis[y.to])dfs(y.to),fl=1;
	if(!fl)for(auto y:son1[x])if(!vis[y.to])dfs(y.to);
}
int ct;
void solve()
{
	ans.clear(),all.clear();
	for(int i=1;i<=n;i++)son[i].clear(),bel[i].clear(),op[i].clear(),prt[i]=i,son1[i].clear();
	for(int i=1;i<=n;i++)pos[i]=0,vis[i]=0,ad[i]=0,ax[i]=0,ay[i]=0,d[i]=0,ned[i]=0,oth[i].clear(),tr[i].clear(),pos[i]=0;
	for(int i=1;i<=m;i++)l1[i]=0;
	for(int i=1;i<=m;i++)
	{
		int x,y,len;
		scanf("%d",&len),l1[i]=len;
		if(len==1)
		{
			scanf("%d",&x);
			if(!ax[x])ax[x]=i;else ay[x]=i;
		}
		else if(len==2)
		{
			scanf("%d %d",&x,&y);
			son[y].push_back((abcd){x,i}),merge(x,y),d[x]++;
			son1[x].push_back((abcd){y,i});
			ad[x]++,ad[y]++;
			if(!ax[x])ax[x]=i;else ay[x]=i;
			if(!ax[y])ax[y]=i;else ay[y]=i;
		}
	}
	for(int i=1;i<=n;i++)bel[gf(i)].push_back(i);
	st[1]=-3,st[2]=-2,st[3]=-1,top=3;
	for(int i=1;i<=n;i++)if(gf(i)==i)
	{
		priority_queue<ab>q;
		tot=0;
		int rt=bel[i][0];
		for(auto j:bel[i])if(ad[j]==1)rt=j;
		dfs(rt);
		for(auto j:bel[i])if(d[j]==0)q.push((ab){j,(int)son[j].size(),pos[j]});
		if(!q.size())
		{
			if(bel[i].size()==1)continue;
			ned[i]=1;
			int len=bel[i].size();
			int x=bel[i][0];
			op[i].push_back((abc){son1[x][0].a,-1});
			int y=son1[x][0].to;
			int now=x,lst=son1[x][0].a;
			while(son[now][0].to!=x)op[i].push_back((abc){son[now][0].a,lst}),lst=son[now][0].a,now=son[now][0].to;
			op[i].push_back((abc){lst,-1});
			all.push_back(i),oth[i].push_back(lst);
			continue;
		}
		while(!q.empty())
		{
			int x=q.top().pos;q.pop();
			if(son[x].size()==2)
			{
				op[i].push_back((abc){ax[x],st[top]});
				op[i].push_back((abc){ay[x],st[top]});
				top--;
			}
			else if(son[x].size()==1)
			{
				int pos=son[x][0].a,pos1;
				if(ax[x]!=pos)pos1=ax[x];else pos1=ay[x];
				op[i].push_back((abc){pos,pos1});
			}
			else
			{
				op[i].push_back((abc){ax[x],ay[x]});
				st[++top]=ax[x];
			}
			for(auto y:son[x])
			{
				d[y.to]--;
				if(!d[y.to])q.push((ab){y.to,(int)son[y.to].size(),pos[y.to]});
			}
		}
		while(top && st[top]>0)oth[i].push_back(st[top]),top--;
		ned[i]=-st[top]-1;
		all.push_back(i);
		st[1]=-3,st[2]=-2,st[3]=-1,top=3;
	}
	sort(all.begin(),all.end(),cmp);
	top=0;
	for(int i=1;i<=m;i++)if(!l1[i])st[++top]=i;
	for(auto i:all)
	{
		if(ned[i]>top){printf("-1\n");return ;}
		for(int j=1;j<=ned[i];j++)temp[j]=st[top-j+1];
		top-=ned[i];
		for(auto &j:op[i])
		{
			if(j.a<0)j.a=temp[-j.a];
			if(j.b<0)j.b=temp[-j.b];
		}
		for(auto j:op[i])ans.push_back(j);
		for(auto j:oth[i])st[++top]=j;
	}
	printf("%d\n",(int)ans.size());
	for(auto j:ans)printf("%d %d\n",j.a,j.b);
}
int main()
{
	// freopen("cluster.in","r",stdin);
	// freopen("cluster.out","w",stdout);
	while(~scanf("%d %d",&n,&m))solve();
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 4ms
memory: 37552kb

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
1 2
0
-1

result:

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

Test #2:

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

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
1 2
1
1 3
1
1 2
0
0
0

result:

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

Test #3:

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

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
1 4
2 3
2
1 4
2 5
2
2 4
5 6
2
2 3
1 4
2
1 5
3 4
2
3 5
1 6
2
1 4
2 3
2
3 4
2 5
2
1 6
3 4
2
1 2
1 3
2
1 2
1 4
2
4 3
1 4
2
2 1
2 3
2
2 1
2 3
2
1 3
1 4
-1
3
2 1
3 1
2 3
3
2 3
4 3
2 4
-1
3
1 3
2 1
2 3
3
2 4
1 2
1 4
1
2 3
1
3 4
1
1 4
0
0
0

result:

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

Test #4:

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

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
1 6
2 3
4 5
3
5 6
3 4
1 7
3
5 6
3 7
2 8
3
4 5
3 6
1 2
3
1 3
4 5
2 6
3
1 8
2 5
4 7
3
2 6
3 5
1 4
3
1 4
2 7
5 6
3
2 8
1 4
3 6
3
4 5
1 2
3 6
3
2 5
4 7
3 6
3
3 4
1 2
5 8
3
1 6
2 5
3 4
3
5 6
1 3
4 7
3
6 7
2 5
4 8
3
1 2
3 6
4 5
3
1 3
5 6
2 7
3
3 7
2 4
6 8
3
1 5
4 6
2 3
3
4 7
1 5
2 3
3
1 6
5 7
4 8
3
4 6
...

result:

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

Test #5:

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

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
4 6
5 8
1 2
3 7
4
4 6
3 8
1 9
5 7
4
1 7
4 5
2 3
8 9
4
5 7
3 4
2 8
1 6
4
3 7
6 8
2 4
1 5
4
2 8
3 7
4 9
1 10
4
7 8
1 5
3 6
2 4
4
1 9
4 6
3 5
2 8
4
4 7
2 3
8 10
5 6
4
1 3
4 7
2 8
5 6
4
2 9
1 7
5 6
3 4
4
2 10
1 9
4 5
3 8
4
2 5
1 3
4 8
6 7
4
1 5
3 8
4 9
2 7
4
3 6
2 9
5 7
1 8
4
2 8
6 7
1 5
3 4
4
2 8
6 7...

result:

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

Test #6:

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

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
1 9
3 6
7 10
2 4
5 8
5
1 3
4 6
2 10
9 11
5 8
5
3 12
1 5
7 11
6 8
4 10
5
3 4
5 9
1 10
6 7
2 8
5
7 8
3 4
1 6
5 10
2 11
5
6 8
3 7
1 12
2 9
5 10
5
4 7
8 9
3 10
1 5
2 6
5
2 4
1 6
5 7
8 9
3 11
5
1 7
2 3
10 11
8 9
4 5
5
8 10
4 5
6 7
2 9
1 3
5
6 7
1 11
4 5
2 3
8 9
5
2 6
4 11
8 9
1 7
3 10
5
7 8
1 10
4 5
3 ...

result:

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

Test #7:

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

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
5 11
10 8
3 10
4 7
1 6
2 9
5
5 4
1 5
7 1
9 1
7 9
-1
8
3 7
4 3
1 4
1 3
5 1
8 1
2 8
2 5
7
4 9
1 8
5 1
7 1
3 5
6 7
2 6
5
4 1
2 7
5 2
3 5
3 4
5
7 1
8 7
6 3
2 6
2 8
5
1 9
2 6
3 10
5 7
8 11
6
1 6
1 5
3 1
4 1
2 4
2 3
-1
6
7 12
2 3
1 11
5 10
6 8
4 9
3
7 6
5 7
3 5
8
5 6
8 6
5 8
1 5
7 5
1 9
4 7
3 4
6
5 9
2 ...

result:

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

Test #8:

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

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
2 9
1 2
4 2
1 4
7
1 11
7 10
5 6
5 7
4 9
2 3
8 12
7
8 13
3 15
9 14
1 4
6 12
2 5
7 11
-1
7
7 10
1 5
3 1
3 11
4 8
6 9
2 12
7
10 13
3 14
5 8
1 7
1 6
4 12
9 11
7
1 6
3 1
10 1
8 10
4 8
7 3
4 7
7
5 12
7 10
8 9
2 11
6 2
3 6
1 4
7
2 10
4 6
5 11
3 4
7 4
7 9
3 5
7
4 1
4 6
2 7
5 9
8 5
10 5
8 10
7
4 5
3 8
2 9
...

result:

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

Test #9:

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

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
5 10
1 11
14 16
3 6
9 15
4 8
9
3 8
12 9
2 12
4 10
7 13
1 11
5 1
6 1
5 6
-1
8
1 16
5 6
3 9
2 10
8 13
11 14
4 7
12 15
9
7 15
6 14
1 9
5 10
8 12
11 8
13 8
4 13
2 11
9
3 1
7 1
5 7
4 3
4 5
8 4
9 4
2 8
2 9
7
2 6
1 2
8 2
10 1
4 10
5 8
4 5
8
7 9
2 11
4 16
3 8
10 12
5 13
1 6
14 15
10
5 8
3 5
7 5
4 3
4 7
1 ...

result:

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

Test #10:

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

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
7 9
6 8
5 12
4 11
1 4
2 1
3 2
3 1
10 3
13 3
10 13
11
11 12
1 5
2 1
8 1
3 2
6 3
4 11
9 11
4 6
13 9
8 13
9
11 14
7 10
8 12
1 17
13 16
9 15
2 3
5 6
4 18
8
4 12
7 11
6 7
6 8
2 6
9 6
5 9
2 5
9
3 11
6 12
2 7
2 6
4 10
9 17
15 16
5 14
1 13
13
7 4
11 7
11 4
1 11
10 11
1 10
2 1
8 2
8 1
5 8
6 8
9 6
5 9
8
5 ...

result:

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

Test #11:

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

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
1 5
7 8
2 14
6 15
9 11
10 13
4 18
16 19
3 17
7
7 11
4 15
5 13
9 12
1 19
6 10
2 16
-1
10
7 17
13 16
1 3
2 12
9 14
8 18
10 15
5 4
5 19
6 11
11
4 19
5 6
5 13
10 12
15 16
3 17
1 9
8 14
7 8
18 7
18 8
7
8 16
12 18
6 13
10 14
1 3
17 19
5 9
10
9 16
4 6
8 12
7 14
10 17
3 13
5 3
1 5
2 15
11 18
10
8 12
10 13...

result:

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

Test #12:

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

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
9 10
3 6
15 12
11 15
5 11
8 11
7 8
13 7
5 13
13
12 15
7 8
6 9
4 5
2 13
1 2
14 2
10 14
3 10
16 10
11 16
17 3
1 17
10
6 17
3 21
10 18
7 9
2 14
16 20
5 11
4 12
1 8
13 15
11
2 9
12 11
8 12
15 3
8 15
1 10
13 1
14 1
7 14
5 7
5 13
10
5 11
16 8
5 16
7 10
14 18
3 6
12 17
4 15
2 19
9 13
11
7 10
7 12
1 7
4 7...

result:

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

Test #13:

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

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
8 23
11 14
6 10
3 20
5 22
7 21
4 17
24 25
1 12
2 16
13 19
9 18
11
1 15
9 7
6 16
4 6
4 9
12 13
17 18
2 11
14 2
10 14
10 2
9
5 11
10 11
3 10
6 3
5 6
1 5
13 1
12 13
12 5
10
7 13
12 13
4 12
6 4
8 5
14 5
6 14
3 8
1 3
1 7
12
11 24
7 14
5 19
1 10
12 21
16 25
2 6
4 20
8 22
9 17
3 13
15 18
11
2 12
4 5
8 4...

result:

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

Test #14:

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

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

result:

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

Test #15:

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

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

result:

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

Test #16:

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

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
4 21
11 17
5 6
2 3
2 14
19 2
8 19
8 2
10 15
9 10
12 8
13 8
9 13
12 22
13
6 22
1 20
11 12
4 8
10 16
24 15
13 24
19 13
17 2
14 17
3 14
3 19
18 23
12
10 13
7 12
8 18
5 8
15 16
23 24
6 22
9 14
2 3
17 2
19 2
17 19
15
6 17
7 6
13 6
7 13
2 7
14 7
12 14
11 3
15 3
11 12
10 11
16 11
10 15
5 16
2 5
16
15 19...

result:

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

Test #17:

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

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

result:

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

Test #18:

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

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

result:

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

Test #19:

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

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
12 5
7 12
7 5
2 7
6 7
19 6
2 19
9 2
11 2
10 9
18 10
1 18
1 11
3 1
14 3
14 1
13 14
16 14
13 16
21
15 16
9 18
3 20
10 21
5 6
4 14
8 25
17 23
11 17
24 17
12 11
26 24
12 26
19 12
22 12
13 22
1 13
1 19
2 1
7 2
7 1
14
10 12
6 13
16 23
14 16
17 14
17 16
11 17
15 17
2 11
19 2
7 19
4 15
20 4
7 20
-1
16
5 ...

result:

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

Test #20:

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

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

result:

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

Test #21:

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

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

result:

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

Test #22:

score: 0
Accepted
time: 10ms
memory: 38900kb

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
36 45
29 22
29 31
37 41
33 75
27 62
19 23
17 35
3 47
44 50
58 44
77 44
58 77
66 58
46 66
46 58
1 46
65 46
16 65
1 16
57 1
70 57
53 70
53 1
25 53
2 25
2 53
14 2
12 14
71 12
24 71
24 2
34 24
39 34
39 24
42 39
13 42
13 39
6 13
73 13
11 3
74 3
76 74
51 76
48 51
56 48
56 73
7 11
6 7
40 56
52 56
63 40
...

result:

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

Test #23:

score: 0
Accepted
time: 18ms
memory: 37804kb

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

result:

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

Test #24:

score: 0
Accepted
time: 150ms
memory: 60956kb

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
72220 199994
127457 199994
71505 72220
29499 71505
65022 127457
1518 65022
160228 1518
43842 160228
4397 29499
144691 29499
43842 144691
177024 43842
197462 43842
4397 177024
179113 197462
75136 4397
165356 4397
174394 165356
174394 179113
107339 75136
145985 107339
7...

result:

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

Test #25:

score: 0
Accepted
time: 157ms
memory: 54536kb

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
78606 55030
188746 78606
51089 145236
197976 51089
175694 197976
40251 199939
183820 199939
124248 183820
2907 124248
76171 2907
116721 76171
92004 116721
92004 188746
100156 40251
38005 92004
113279 92004
100156 113279
88774 100156
190551 100156
38005 190551
56580 88774
175374 56580
158659 1...

result:

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

Test #26:

score: 0
Accepted
time: 147ms
memory: 53728kb

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
89684 177658
177708 198873
2295 177708
190108 2295
28332 199158
49017 199158
28332 89684
151437 49017
145189 28332
155756 28332
145189 151437
29380 145189
196194 145189
169656 29380
129693 169656
192484 129693
155756 192484
124223 196194
118489 124223
5457 155756
90928 155756
5457 118489
1578...

result:

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

Test #27:

score: 0
Accepted
time: 133ms
memory: 53404kb

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
142460 128554
153991 60678
97518 153991
97518 142460
29045 175509
131028 153733
27632 164619
173728 27632
55651 173728
10882 55651
49357 149784
9468 81746
9468 49357
82537 27653
172059 10316
155953 172059
159307 155953
82537 159307
145599 171805
170314 145599
16605 170314
162045 16605
21080 1...

result:

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

Test #28:

score: 0
Accepted
time: 70ms
memory: 46896kb

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
12320 101989
12320 85979
10725 82927
869 124187
91353 119365
82664 126557
50443 82664
147221 115173
39134 147221
39134 87007
36299 149000
96636 103175
50832 96636
113313 64371
32187 113313
73410 142185
55244 86508
80875 81742
101496 1205
27300 101496
103012 6371
85435 103012
11193 81996
13193...

result:

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

Test #29:

score: 0
Accepted
time: 143ms
memory: 63156kb

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
17813 200000
72626 200000
134563 72626
192276 17813
165752 192276
5262 199999
30899 199999
5262 165752
37687 30899
43247 5262
181997 5262
37687 181997
24936 37687
190474 37687
130329 24936
130371 130329
43247 130371
24554 43247
140583 43247
142584 24554
142584 190474
121932 142584
151951 1425...

result:

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