QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#373461#2830. Data StructurePetroTarnavskyiAC ✓220ms65368kbC++204.7kb2024-04-01 18:08:272024-04-01 18:08:27

Judging History

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

  • [2024-04-01 18:08:27]
  • 评测
  • 测评结果:AC
  • 用时:220ms
  • 内存:65368kb
  • [2024-04-01 18:08:27]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

const int N = 1 << 18;

int n, m;

vector<PII> ans;
VI cols[N];
set<int> freeCols;
VI where[N];

int whereUp(int v)
{
	for(int col : where[v])
	{
		assert(SZ(cols[col]) != 0);
		if(cols[col].back() == v)
			return col;
		assert(cols[col][0] == v);
	}
	assert(0);
}
void delCol(int v, int col)
{
	int id = -1;
	FOR(i, 0, SZ(where[v]))
		if(where[v][i] == col)
			id = i;
	assert(id != -1);
	where[v] = {where[v][id ^ 1]};
}

void move(int from, int to)
{
	assert(from != to);
	ans.PB(MP(from, to));
	
	if(SZ(cols[to]) == 0)
		freeCols.erase(to);
	if(SZ(cols[from]) == 1)
		freeCols.insert(from);
	
	
	int v = cols[from].back();

	cols[from].pop_back();
	cols[to].PB(v);
	
	delCol(v, from);
	where[v].PB(to);	
}
bool solve(int v)
{
	//cout << v << " " << where[v][0] << " " << where[v][1] << "\n";
	//in one col
	if(where[v][0] == where[v][1])
		return 1;
		
	//cerr << v << "\n";
	for(int col : where[v])
		assert(cols[col].back() == v);
	
	int id = -1;
	FOR(i, 0, 2)
	{
		if(SZ(cols[where[v][i]]) == 1)
			id = i;
	}
	if(id == -1)
	{
		if(SZ(freeCols) == 0)
			return 0;
		int to = *freeCols.begin();
		int fr0 = where[v][0];
		int fr1 = where[v][1];
		move(fr0, to);
		move(fr1, to);
	}
	else
		move(where[v][id ^ 1], where[v][id]);
	
	return 1;
}
int cnt[N];
bool solve(VI vs)
{
	if(SZ(vs) == 1)
		return solve(vs[0]);
	//FOR(i, 0, SZ(vs))
	//	cerr << vs[i] << " ";
	//cerr << "\n";
	//FOR(i, 0, SZ(vs))
	//	cerr << cnt[vs[i]] << " ";
	//cerr << "\n";
	
	FOR(i, 0, SZ(vs))
	{
		int j = i;
		while(j < SZ(vs) && cnt[vs[j]] <= 0)
			j++;
		assert(j != SZ(vs));
		
		RFOR(it, j + 1, i)
		{
			if(!solve(vs[it]))
				return 0;
		}
			
		i = j;
		while(j < SZ(vs) && cnt[vs[j]] >= -1)
			j++;
		
		FOR(it, i + 1, j)
		{
			if(!solve(vs[it]))
				return 0;
		}
		i = j - 1;
	}
	return 1;
}



VI component;
VI g[N], gr[N];
bool used[N];
void dfs(int v)
{
	used[v] = 1;
	component.PB(v);
	for(int to : g[v])
		if(!used[to])
			dfs(to);
	for(int to : gr[v])
		if(!used[to])
			dfs(to);
}


void clear()
{
	FOR(i, 0, n)
	{
		g[i].clear();
		gr[i].clear();
		cnt[i] = used[i] = 0;
		
		where[i].clear();
		cols[i].clear();
	}
	component.clear();
	ans.clear();
	freeCols.clear();
}
void bad()
{
	cout << "-1\n";
	clear();
}

void solve()
{
	FOR(i, 0, m)
	{
		if(SZ(cols[i]) != 2)
			continue;
		int solvedFirst = cols[i][1];
		int solvedSecond = cols[i][0];
		
		if(solvedFirst == solvedSecond)
			continue;
		
		cnt[solvedFirst]++;
		cnt[solvedSecond]--;
		
		g[solvedFirst].PB(solvedSecond);
		gr[solvedSecond].PB(solvedFirst);
	}
	FOR(i, 0, n)
	{
		if(SZ(g[i]) + SZ(gr[i]) == 0)
		{
			assert(solve(i));
			used[i] = 1;
		}
	}
	FOR(t, 0, 2)
	{
		FOR(i, 0, n)
		{
			if(!used[i] && SZ(g[i]) + SZ(gr[i]) == 1)
			{			
				component.clear();
				dfs(i);
				
				if(!solve(component))
				{
					if(t == 0)
					{
						for(int v : component)
							used[v] = 0;
					}
					else
					{
						bad();
						return;
					}
				}
			}
		}
	}		
	FOR(i, 0, n)
	{
		if(!used[i] && cnt[i] > 0)
		{
			component.clear();
			dfs(i);
			
			assert(component[0] == i);
			component.erase(component.begin());
			if(!solve(i))
			{
				bad();
				return;
			}
			
			for(int to : g[i])
				cnt[to] = cnt[to] + 1;
			if(!solve(component))
			{
				bad();
				return;
			}
		}
	}
	FOR(i, 0, n)
	{
		if(!used[i])
		{
			assert(cnt[i] == 0);
			
			component.clear();
			dfs(i);
			
			if(SZ(freeCols) == 0)
			{
				bad();
				return;
			}
			
			assert(component[0] == i);
			component.erase(component.begin());
			component.PB(i);
			
			move(whereUp(i), *freeCols.begin());
			
			cnt[i]--;
			for(int to : g[i])
				cnt[to] = cnt[to] + 1;
			if(!solve(component))
			{
				bad();
				return;
			}
		}
	}
	
	cout << SZ(ans) << "\n";
	for(auto [from, to] : ans)
	{
		cout << from + 1 << " " << to + 1 << "\n";
	}
	clear();
}


int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	
	while(cin >> n >> m)
	{
		FOR(i, 0, m)
		{
			int k;
			cin >> k;
			VI a(k);
			FOR(j, 0, k)
			{
				cin >> a[j];
				a[j]--;
				where[a[j]].PB(i);
			}
			if(k == 0)
				freeCols.insert(i);
			
			cols[i] = a;
		}
		solve();
	}
	
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 7672kb

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

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

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 1
4 1
2 4
-1
3
2 3
1 2
1 3
3
1 3
2 1
2 3
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: 2ms
memory: 5736kb

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

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

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

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

result:

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

Test #8:

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

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
4 9
2 3
8 12
5 6
7 10
5 7
7
8 13
3 15
9 14
1 4
6 12
2 5
7 11
-1
7
7 10
4 8
6 9
2 12
1 5
3 1
3 11
7
10 13
3 14
5 8
4 12
9 11
1 7
1 6
7
1 6
3 1
10 1
7 3
8 10
4 8
4 7
7
5 12
7 10
8 9
1 4
2 11
6 2
3 6
7
2 10
4 6
5 11
3 1
7 1
3 5
7 9
7
2 7
5 9
4 1
4 6
8 2
10 2
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: 32ms
memory: 5720kb

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
4 10
7 13
1 11
12 9
2 12
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 1
13 1
2 11
4 13
9
8 1
9 1
2 8
2 9
3 2
7 2
4 3
5 7
4 5
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: 26ms
memory: 7672kb

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

result:

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

Test #11:

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

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

result:

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

Test #12:

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

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

result:

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

Test #13:

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

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

result:

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

Test #14:

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

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

result:

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

Test #15:

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

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
9 5
24 21
8 24
10 8
13 10
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
3 15
5 6
4 21
14 20
1 17
8 13
8 11
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 1
23 1
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: 31ms
memory: 7920kb

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

result:

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

Test #17:

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

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

result:

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

Test #18:

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

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

result:

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

Test #19:

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

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

result:

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

Test #20:

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

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

result:

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

Test #21:

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

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

result:

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

Test #22:

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

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
37 41
33 75
27 62
17 35
3 47
44 50
19 23
29 22
29 31
40 3
52 3
63 40
9 63
26 17
60 17
10 26
72 10
9 72
52 60
32 9
61 9
38 32
15 19
20 19
30 15
30 38
68 27
79 27
20 68
78 61
78 79
1 20
65 20
16 65
1 16
8 1
21 1
69 8
55 29
67 29
55 69
54 67
21 54
11 21
74 21
7 11
6 30
73 30
6 7
76 74
51 76
48...

result:

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

Test #23:

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

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

result:

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

Test #24:

score: 0
Accepted
time: 211ms
memory: 59096kb

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
33532 199993
149868 199993
55718 149868
55718 174021
40140 55718
154492 55718
98071 154492
33532 98071
3409 40140
127577 3409
146781 33532
183763 33532
127577 146781
177569 183763
39870 177569
128051 39870
40416 128051
47653 40416
24457 47653
139428 24457
94458 139428
3940 127577
78541 127577...

result:

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

Test #25:

score: 0
Accepted
time: 220ms
memory: 50948kb

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
106581 195508
61879 106581
58652 199938
173762 199938
61879 173762
10636 58652
53630 61879
101776 61879
160710 53630
38522 160710
10636 38522
154767 10636
183655 10636
42645 154767
36502 42645
36502 101776
139484 183655
17420 36502
148363 36502
98577 17420
145079 98577
139484 145079
65955 148...

result:

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

Test #26:

score: 0
Accepted
time: 194ms
memory: 48832kb

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
83406 199157
84174 199157
26569 84174
26569 188145
51106 83406
39533 26569
52620 26569
39533 51106
5736 39533
146489 39533
105904 5736
87709 105904
52620 87709
154600 146489
101799 154600
140533 101799
170499 140533
37206 52620
61933 52620
37206 170499
147032 37206
175514 37206
116054 147032
...

result:

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

Test #27:

score: 0
Accepted
time: 218ms
memory: 46220kb

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
115305 173688
59173 162528
154636 191315
2345 134194
35960 172070
81231 144419
41297 67516
45199 54669
177867 185539
5835 134098
26450 186598
4023 39925
31497 116217
131028 153733
142872 179043
55368 167022
24444 172578
21069 131898
13697 86705
54857 57867
104032 105478
30688 82920
107437 156...

result:

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

Test #28:

score: 0
Accepted
time: 102ms
memory: 30564kb

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
4709 37327
12514 126560
40604 80635
20806 112227
25767 46609
24650 46902
80991 141613
49054 140135
14362 130535
22358 33893
9919 89093
102297 136505
126469 141173
78525 134207
125222 149492
7809 66841
2232 8426
27574 133665
67047 124348
52285 116414
60881 146565
144720 147826
49620 138835
297...

result:

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

Test #29:

score: 0
Accepted
time: 179ms
memory: 65368kb

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
171410 199999
181365 199999
97712 171410
52612 97712
119503 52612
138016 119503
28740 138016
21514 200000
91173 200000
169576 21514
36185 169576
8836 36185
74434 8836
28740 74434
77064 91173
11747 28740
130769 28740
77064 130769
185560 11747
72711 77064
193153 77064
77786 72711
77786 185560
9...

result:

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