QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#429719#5239. Mędrcy [A]qwqUwU_5 22ms4136kbC++202.2kb2024-06-02 19:36:102024-06-02 19:36:10

Judging History

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

  • [2024-06-02 19:36:10]
  • 评测
  • 测评结果:5
  • 用时:22ms
  • 内存:4136kb
  • [2024-06-02 19:36:10]
  • 提交

answer

#include<bits/stdc++.h>
#define pb push_back
#define P make_pair
#define fi first
#define se second
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define bit(s,x) (((s)>>(x))&1)
#define pnp(s) __builtin_popcount(s)
#define lb(s) (s&-s)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
inline ll read(){
	ll x=0,f=1,c=getchar();
	while(c<'0'||c>'9')f=(c=='-'?-1:1),c=getchar();
	while(c>='0' && c<='9')x=x*10 + c-'0',c=getchar();
	return x*f;
}
const int N=1e3+3;
const int mod=998244353;
inline void Ad(int &x,int y){x=x+y>=mod?x+y-mod:x+y;}
int n,m,k;
bitset<N>bs,ans;int res;
pii p[3*N];
int d[N];
bool vis[N];
int inq[N];
vector<int>G[N],vec;
inline void dfs2(int u){
	vis[u]=1;vec.pb(u);
	for(auto v:G[u])if(!vis[v])dfs2(v);
}
inline void dfs(int k){
	rep(i,1,n)d[i]=0;
	rep(i,1,m)if(!bs[p[i].fi] && !bs[p[i].se])++d[p[i].fi],++d[p[i].se];
	int bst=1;
	rep(i,2,n)if(d[bst]<d[i])bst=i;
	if(d[bst]<=2){
		bitset<N> tmp(bs);
		rep(i,1,n)vis[i]=0,G[i].clear();
		rep(i,1,m)if(!bs[p[i].fi] && !bs[p[i].se]){
			int u=p[i].fi,v=p[i].se;
			G[u].pb(v),G[v].pb(u);
		}
		rep(i,1,n)if(!vis[i] && !bs[i] && d[i]==1){
			vec.clear(); dfs2(i);
			int m=vec.size();k += m>>1;
			for(int i=m&1;i<m;i+=1+(m&1))bs.set(vec[i]);
		}
		rep(i,1,n)if(!vis[i] && !bs[i] && d[i]==2){
			vec.clear(); dfs2(i);
			int m=vec.size();k += (m+1)>>1;
			rep(i,0,m-1)bs.set(vec[i]);
		}
		if(k<res) res=k,ans.reset();
		if(res==k)ans|=bs;
		bs=tmp;
		return ;
	}
	bs.set(bst);dfs(k+1);bs.reset(bst);
	vector<int>T;
	rep(i,1,m)if(!bs[p[i].fi] && !bs[p[i].se] && (p[i].fi==bst || p[i].se==bst)){
		if(p[i].se==bst)swap(p[i].fi,p[i].se);
		++k;bs.set(p[i].se);
		T.pb(i);
	}
	dfs(k);
	for(auto i:T)bs.reset(p[i].se);
}
inline void solve(){
	n=read(),m=read(),k=read();
	bs.reset(),ans.reset();res=n;
	rep(i,1,m){
		p[i].fi=read(),p[i].se=read();
	}
	dfs(0);
	if(res>k){ puts("-1"); return ; }
	printf("%d %d\n",res,ans.count());
	for(int i=ans._Find_first();i<=n;i=ans._Find_next(i))printf("%d ",i);
	puts("");
}
int main(){
	//freopen("data.in","r",stdin);
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	int T=read();while(T--)solve();
}

详细

Subtask #1:

score: 1
Accepted

Test #1:

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

input:

136
9 37 11
2 7
2 5
2 5
6 8
2 4
2 9
4 5
6 8
6 7
3 9
3 6
3 8
1 9
2 9
4 6
2 4
1 4
7 9
7 9
4 7
3 6
4 5
2 7
1 5
6 9
4 9
4 5
2 7
3 9
1 9
2 7
5 7
1 2
2 3
1 8
3 8
1 3
7 1 13
4 6
3 36 2
2 3
2 3
1 2
2 3
1 3
1 3
1 3
1 2
1 2
1 2
1 2
1 2
1 3
1 2
1 3
1 3
1 2
1 3
1 2
1 3
1 2
2 3
1 2
1 3
1 3
2 3
1 3
2 3
2 3
1 2
1 ...

output:

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

result:

ok 243 lines

Test #2:

score: 1
Accepted
time: 1ms
memory: 3836kb

input:

133
5 41 5
1 2
3 5
1 2
4 5
4 5
1 4
1 4
3 4
4 5
1 5
2 5
3 4
3 4
3 5
2 3
3 4
2 4
1 4
2 4
1 3
3 4
2 5
3 5
1 4
1 5
2 4
2 5
4 5
1 3
2 5
3 5
1 5
3 4
2 4
3 5
3 5
1 2
2 3
1 4
2 5
1 3
10 23 12
4 6
3 7
3 8
1 8
1 2
1 3
5 8
4 10
1 10
3 9
7 10
2 5
5 8
3 7
2 9
3 4
2 8
3 9
2 6
3 9
3 10
6 10
7 10
12 31 7
1 10
6 9
1...

output:

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

result:

ok 237 lines

Test #3:

score: 1
Accepted
time: 1ms
memory: 3876kb

input:

128
11 16 6
3 5
7 9
5 8
7 9
8 10
1 10
3 8
1 6
4 5
4 8
5 6
7 11
8 11
2 6
2 6
2 5
7 15 4
1 7
2 5
4 6
4 7
2 3
5 6
1 7
1 6
1 3
2 5
1 4
3 5
2 4
3 4
4 7
4 18 3
1 2
1 4
3 4
1 3
1 3
1 4
3 4
3 4
2 4
2 4
2 4
2 3
1 2
1 2
2 4
3 4
3 4
1 2
7 11 14
5 6
2 7
2 4
3 7
6 7
2 5
3 4
3 7
1 7
2 4
6 7
9 24 1
4 6
6 7
1 6
5 6...

output:

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

result:

ok 256 lines

Test #4:

score: 1
Accepted
time: 1ms
memory: 3808kb

input:

135
10 16 6
3 9
1 2
1 8
2 6
3 4
5 8
1 6
1 6
3 6
3 9
4 5
2 6
3 5
9 10
9 10
6 7
10 3 6
2 4
1 6
2 9
7 11 6
1 3
1 4
3 5
4 6
4 5
3 7
1 5
6 7
3 6
3 6
1 2
6 10 8
1 5
1 2
3 5
2 3
2 4
4 5
1 3
3 6
5 6
1 2
8 17 9
1 6
5 6
7 8
4 7
6 8
5 7
4 7
5 6
2 7
1 2
1 5
4 6
5 8
6 7
4 8
4 8
4 7
9 9 4
1 8
4 7
7 9
1 3
3 8
1 2
...

output:

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

result:

ok 270 lines

Test #5:

score: 1
Accepted
time: 1ms
memory: 3780kb

input:

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

output:

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

result:

ok 251 lines

Test #6:

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

input:

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

output:

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

result:

ok 229 lines

Test #7:

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

input:

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

output:

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

result:

ok 232 lines

Test #8:

score: 1
Accepted
time: 1ms
memory: 3836kb

input:

135
3 3 2
1 3
1 2
2 3
5 4 11
1 3
3 5
1 5
2 4
12 19 15
6 12
5 8
1 2
1 3
10 12
2 4
1 7
5 11
3 7
8 9
3 4
8 11
2 3
2 7
9 11
4 7
6 10
5 9
1 4
8 9 2
4 6
2 7
1 2
3 6
2 8
1 7
1 8
3 4
7 8
9 12 10
2 5
1 6
3 8
2 6
4 5
1 5
7 9
4 6
1 4
5 6
1 2
2 4
7 11 5
3 6
2 6
6 7
2 3
1 6
4 5
2 7
1 3
1 7
1 2
3 7
12 21 10
6 9
2...

output:

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

result:

ok 230 lines

Test #9:

score: 1
Accepted
time: 1ms
memory: 4068kb

input:

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

output:

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

result:

ok 259 lines

Test #10:

score: 1
Accepted
time: 1ms
memory: 4040kb

input:

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

output:

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

result:

ok 246 lines

Test #11:

score: 1
Accepted
time: 1ms
memory: 3832kb

input:

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

output:

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

result:

ok 253 lines

Test #12:

score: 1
Accepted
time: 1ms
memory: 4064kb

input:

333
3 2 5
1 2
2 3
3 3 8
1 3
2 3
1 3
3 7 11
2 3
1 3
1 3
1 2
1 3
1 3
2 3
3 8 3
1 2
2 3
1 2
1 3
1 3
2 3
1 2
1 2
3 2 2
1 2
1 2
3 3 15
1 3
1 2
1 2
3 9 5
2 3
1 2
1 3
2 3
1 3
1 2
1 2
1 3
1 3
3 1 14
1 2
3 3 11
1 3
1 2
2 3
3 2 14
1 3
2 3
3 8 5
2 3
1 3
1 2
1 3
2 3
1 3
1 2
1 2
3 5 9
1 2
1 2
1 3
1 3
1 3
3 5 5
2...

output:

1 1
2 
1 1
3 
2 3
1 2 3 
2 3
1 2 3 
1 2
1 2 
1 1
1 
2 3
1 2 3 
1 2
1 2 
2 3
1 2 3 
1 1
3 
2 3
1 2 3 
1 1
1 
1 1
3 
-1
2 3
1 2 3 
1 1
2 
2 3
1 2 3 
2 3
1 2 3 
2 3
1 2 3 
2 3
1 2 3 
1 2
1 2 
1 1
3 
2 3
1 2 3 
1 2
1 3 
1 1
2 
1 1
2 
1 1
3 
1 2
1 3 
1 1
1 
2 3
1 2 3 
1 1
2 
2 3
1 2 3 
2 3
1 2 3 
1 2
2 3...

result:

ok 646 lines

Subtask #2:

score: 1
Accepted

Test #13:

score: 1
Accepted
time: 1ms
memory: 3780kb

input:

139
11 16 6
3 4
1 3
5 7
3 6
3 9
7 10
3 8
1 2
4 8
1 11
4 8
4 9
3 6
4 9
5 9
1 6
8 23 11
2 4
4 8
3 6
4 5
1 3
5 7
3 8
2 5
1 6
1 5
5 8
6 7
1 3
3 5
6 7
7 8
6 8
5 8
4 6
4 8
2 3
1 5
2 8
11 31 1
5 11
3 11
5 7
1 9
3 5
3 5
1 2
1 5
5 7
9 10
2 6
2 7
2 9
5 9
1 11
5 8
4 8
5 6
4 10
3 10
2 9
7 11
5 9
2 6
8 9
9 10
8 ...

output:

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

result:

ok 257 lines

Test #14:

score: 1
Accepted
time: 1ms
memory: 3776kb

input:

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

output:

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

result:

ok 233 lines

Test #15:

score: 1
Accepted
time: 1ms
memory: 3780kb

input:

138
12 26 14
6 12
3 10
7 9
3 5
7 12
2 11
1 5
10 11
4 11
2 4
5 10
2 8
2 9
5 9
7 11
7 11
1 3
4 7
5 7
1 3
2 7
3 6
7 10
6 11
5 12
6 12
5 32 11
2 5
4 5
4 5
2 3
2 4
2 4
2 4
3 4
3 5
2 4
1 3
1 5
2 3
2 4
1 2
2 3
3 4
2 3
2 5
3 5
2 5
2 3
3 4
1 2
3 4
1 4
2 4
1 3
1 4
3 4
1 4
2 5
5 35 10
3 5
3 4
3 4
3 4
1 3
1 5
1...

output:

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

result:

ok 276 lines

Test #16:

score: 1
Accepted
time: 1ms
memory: 3788kb

input:

133
10 22 6
5 8
1 6
3 5
1 6
1 4
6 8
3 7
1 4
5 8
3 6
9 10
2 8
5 10
4 7
7 10
4 5
2 9
2 6
3 6
1 10
5 8
3 10
12 1 8
4 12
7 5 14
4 5
2 7
1 2
6 7
1 2
8 27 5
6 8
2 6
2 7
2 3
4 6
4 8
1 3
1 2
4 5
3 4
3 8
4 8
1 8
2 3
5 6
4 5
6 7
4 5
2 7
1 5
2 6
6 7
2 5
1 8
2 3
2 6
2 3
6 37 3
2 5
2 5
1 2
2 4
4 6
2 5
2 5
3 5
1 ...

output:

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

result:

ok 266 lines

Test #17:

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

input:

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

output:

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

result:

ok 238 lines

Test #18:

score: 1
Accepted
time: 1ms
memory: 3832kb

input:

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

output:

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

result:

ok 239 lines

Test #19:

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

input:

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

output:

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

result:

ok 224 lines

Test #20:

score: 1
Accepted
time: 1ms
memory: 4076kb

input:

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

output:

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

result:

ok 228 lines

Test #21:

score: 1
Accepted
time: 1ms
memory: 3788kb

input:

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

output:

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

result:

ok 256 lines

Test #22:

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

input:

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

output:

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

result:

ok 262 lines

Test #23:

score: 1
Accepted
time: 1ms
memory: 3780kb

input:

134
5 10 14
3 4
3 5
2 4
2 3
4 5
1 2
1 5
1 5
1 2
3 4
8 16 7
2 4
4 7
2 8
5 6
3 6
3 8
2 3
1 8
1 5
5 8
1 7
4 7
5 7
4 6
3 6
1 2
11 22 4
8 11
2 10
4 7
2 10
2 11
5 7
3 5
1 8
6 9
8 9
1 5
6 7
3 4
10 11
1 4
3 11
5 9
2 6
6 9
3 10
1 8
4 7
11 22 7
2 5
1 6
9 11
4 7
5 10
3 6
1 6
5 10
4 6
3 8
2 4
10 11
9 10
3 8
1 7...

output:

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

result:

ok 245 lines

Test #24:

score: 1
Accepted
time: 1ms
memory: 3792kb

input:

83
12 33 3
4 7
6 10
9 10
1 12
4 8
9 12
5 10
5 12
2 11
4 11
4 7
4 6
3 5
4 9
10 12
2 6
6 10
1 12
1 5
8 9
3 12
2 11
2 6
3 8
1 8
10 11
4 9
2 7
6 7
1 12
8 9
8 9
9 12
12 21 9
2 4
4 12
4 8
5 11
4 8
5 12
10 11
3 7
3 9
3 6
2 6
6 9
2 12
4 5
5 11
1 4
4 5
11 12
9 12
4 8
1 7
12 19 8
5 8
5 12
8 12
4 5
1 10
4 12
2...

output:

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

result:

ok 129 lines

Subtask #3:

score: 1
Accepted

Test #25:

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

input:

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

output:

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

result:

ok 132 lines

Test #26:

score: 1
Accepted
time: 2ms
memory: 3720kb

input:

63
10 67 30
4 6
6 10
8 10
2 6
6 9
3 5
4 5
5 6
1 8
5 8
5 7
2 9
1 7
6 7
2 10
7 8
1 7
1 10
7 9
1 9
7 10
2 6
1 3
1 8
6 10
1 7
3 4
4 5
3 4
9 10
4 10
2 4
4 9
4 9
1 7
2 8
4 9
5 7
3 7
4 10
7 10
5 7
4 7
3 5
6 9
3 8
1 6
9 10
2 7
1 2
2 9
6 10
4 9
7 8
6 7
2 5
2 6
1 5
4 9
6 7
6 9
3 4
2 10
4 9
5 9
6 9
4 5
19 65 3...

output:

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

result:

ok 126 lines

Test #27:

score: 1
Accepted
time: 2ms
memory: 4064kb

input:

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

output:

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

result:

ok 132 lines

Test #28:

score: 1
Accepted
time: 2ms
memory: 3832kb

input:

66
10 39 30
4 7
3 9
1 5
5 9
3 10
3 6
4 7
3 4
1 9
2 10
6 9
1 9
2 6
1 4
1 3
2 7
2 4
2 6
7 9
1 4
1 6
2 10
4 7
1 3
1 10
7 8
3 4
7 8
3 9
8 9
3 5
3 4
2 4
2 4
3 4
8 9
3 4
6 9
2 6
17 52 30
6 10
1 13
3 7
7 9
2 17
11 17
3 10
4 17
9 17
5 13
2 8
2 6
9 10
7 17
5 7
8 10
11 13
4 12
5 14
1 2
2 12
6 15
5 12
7 17
14 ...

output:

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

result:

ok 132 lines

Test #29:

score: 1
Accepted
time: 22ms
memory: 3776kb

input:

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

output:

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

result:

ok 119 lines

Test #30:

score: 1
Accepted
time: 11ms
memory: 3784kb

input:

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

output:

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

result:

ok 120 lines

Test #31:

score: 1
Accepted
time: 1ms
memory: 3836kb

input:

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

output:

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

result:

ok 120 lines

Test #32:

score: 1
Accepted
time: 2ms
memory: 3772kb

input:

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

output:

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

result:

ok 112 lines

Test #33:

score: 1
Accepted
time: 16ms
memory: 3872kb

input:

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

output:

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

result:

ok 119 lines

Test #34:

score: 1
Accepted
time: 2ms
memory: 3840kb

input:

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

output:

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

result:

ok 117 lines

Test #35:

score: 1
Accepted
time: 2ms
memory: 4064kb

input:

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

output:

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

result:

ok 140 lines

Subtask #4:

score: 1
Accepted

Test #36:

score: 1
Accepted
time: 2ms
memory: 3720kb

input:

67
11 28 30
1 7
1 5
4 11
1 2
2 10
9 11
8 9
7 9
4 8
4 9
5 8
5 7
5 8
2 11
8 10
1 3
2 11
5 8
2 4
7 10
8 11
6 11
2 4
2 11
1 6
10 11
8 11
3 8
10 44 30
5 8
1 4
1 4
3 9
1 4
6 7
3 8
6 7
4 8
4 6
1 2
4 7
1 8
1 5
9 10
2 10
7 8
2 8
1 9
1 5
5 10
1 7
4 6
7 10
2 5
4 8
6 8
8 9
7 10
6 10
4 10
3 5
2 9
6 10
4 8
5 10
5...

output:

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

result:

ok 134 lines

Test #37:

score: 1
Accepted
time: 2ms
memory: 4136kb

input:

67
11 27 30
3 7
6 10
1 11
5 6
4 11
7 10
8 9
3 5
1 8
6 11
3 6
1 7
6 8
2 11
3 6
1 3
5 9
9 10
5 6
6 10
4 11
6 9
5 7
5 6
5 11
8 10
1 6
10 33 30
4 8
4 6
7 9
3 8
6 7
3 4
7 8
1 4
2 10
3 6
2 8
2 9
3 7
1 5
4 7
4 8
1 4
4 9
3 6
3 4
3 8
3 10
4 5
1 4
3 6
7 10
1 3
9 10
2 10
6 8
3 9
2 5
2 7
11 40 30
2 6
7 10
8 9
4...

output:

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

result:

ok 134 lines

Test #38:

score: 1
Accepted
time: 2ms
memory: 3872kb

input:

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

output:

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

result:

ok 134 lines

Test #39:

score: 1
Accepted
time: 2ms
memory: 3836kb

input:

65
17 38 30
3 15
6 17
11 16
1 15
3 14
8 16
3 15
7 8
6 7
1 7
4 11
15 17
2 10
3 17
2 15
9 13
1 5
6 15
1 2
1 14
11 12
9 12
1 6
1 14
2 4
11 16
5 12
2 7
10 15
1 7
11 13
2 16
12 16
6 10
1 17
10 16
4 14
3 4
10 54 30
6 7
7 9
6 7
1 7
6 7
6 7
5 7
1 7
4 7
2 7
2 7
7 9
1 7
1 7
7 9
3 7
3 7
7 10
7 8
1 7
7 9
4 7
6 ...

output:

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

result:

ok 130 lines

Test #40:

score: 1
Accepted
time: 15ms
memory: 3804kb

input:

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

output:

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

result:

ok 123 lines

Test #41:

score: 1
Accepted
time: 6ms
memory: 4060kb

input:

67
17 33 10
2 10
8 17
9 17
2 7
2 7
5 10
11 16
4 9
9 17
4 5
1 11
8 17
2 10
5 10
2 10
9 17
4 5
8 17
5 10
8 16
1 7
8 16
11 16
11 16
4 5
1 7
4 9
1 11
1 7
4 9
2 7
8 16
1 11
16 39 17
5 11
7 10
6 12
6 12
7 10
1 3
2 3
1 3
4 16
5 11
1 16
1 16
5 12
2 8
9 11
2 8
5 12
8 9
6 7
7 10
4 16
5 11
4 10
6 7
6 12
5 12
8...

output:

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

result:

ok 124 lines

Test #42:

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

input:

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

output:

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

result:

ok 108 lines

Test #43:

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

input:

68
19 41 27
2 5
8 11
2 8
13 15
4 10
15 18
8 14
3 18
8 17
6 7
2 11
4 6
9 17
11 17
5 17
10 16
4 16
12 15
2 9
7 16
5 11
2 14
14 17
7 10
3 15
13 18
5 8
12 18
9 14
3 13
9 11
5 14
8 9
11 14
6 16
4 7
6 10
2 17
5 9
3 12
12 13
12 36 24
10 12
5 10
9 11
6 12
9 10
7 8
7 12
8 10
7 9
6 8
5 8
5 12
2 12
2 5
5 11
8 ...

output:

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

result:

ok 116 lines

Test #44:

score: 1
Accepted
time: 3ms
memory: 4036kb

input:

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

output:

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

result:

ok 122 lines

Test #45:

score: 1
Accepted
time: 2ms
memory: 3840kb

input:

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

output:

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

result:

ok 118 lines

Test #46:

score: 1
Accepted
time: 3ms
memory: 3872kb

input:

64
12 24 30
2 7
1 2
9 11
11 12
9 10
10 11
3 4
5 8
2 6
1 4
8 9
6 12
5 11
5 6
3 10
2 5
8 12
6 8
1 7
1 7
9 10
7 12
3 4
3 4
12 24 30
4 6
8 11
5 10
3 4
9 12
5 11
1 5
7 8
5 10
4 7
11 12
2 6
3 9
7 12
9 10
6 8
4 10
3 8
7 9
1 2
1 3
1 11
2 12
2 6
13 25 30
4 11
7 8
5 11
10 13
2 7
2 5
3 4
6 9
8 12
7 12
6 7
6 13...

output:

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

result:

ok 128 lines

Subtask #5:

score: 1
Accepted

Test #47:

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

input:

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

output:

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

result:

ok 128 lines

Test #48:

score: 1
Accepted
time: 2ms
memory: 3716kb

input:

69
10 46 30
6 8
1 10
1 2
2 6
4 9
2 6
1 10
5 6
1 2
1 9
1 6
4 6
1 6
5 6
1 6
2 6
1 7
1 8
7 9
3 4
4 7
3 9
5 6
4 6
7 9
2 6
2 4
4 5
2 6
5 10
3 7
3 10
5 10
3 10
5 6
3 4
3 8
4 7
1 2
3 6
2 6
1 6
2 10
1 3
6 10
3 9
17 42 30
7 12
2 5
4 10
4 11
2 14
8 10
4 9
12 15
3 4
9 16
2 9
4 11
2 10
3 6
4 15
2 4
8 14
3 7
1 1...

output:

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

result:

ok 138 lines

Test #49:

score: 1
Accepted
time: 2ms
memory: 3812kb

input:

65
13 32 30
3 8
6 12
2 9
4 6
3 4
3 10
5 7
11 13
3 10
5 11
9 13
4 13
4 8
9 13
1 5
3 10
8 9
11 12
2 8
1 5
1 5
8 11
6 8
6 11
2 5
9 10
7 13
2 6
4 10
6 10
7 9
9 13
17 56 30
8 12
13 15
8 10
10 17
3 8
1 14
10 13
16 17
9 12
4 5
10 15
2 15
6 17
6 11
8 15
2 14
4 14
5 16
2 15
2 10
16 17
1 11
7 17
7 11
2 10
13 ...

output:

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

result:

ok 130 lines

Test #50:

score: 1
Accepted
time: 2ms
memory: 3780kb

input:

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

output:

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

result:

ok 128 lines

Test #51:

score: 1
Accepted
time: 16ms
memory: 4064kb

input:

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

output:

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

result:

ok 116 lines

Test #52:

score: 1
Accepted
time: 13ms
memory: 3720kb

input:

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

output:

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

result:

ok 128 lines

Test #53:

score: 1
Accepted
time: 1ms
memory: 3772kb

input:

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

output:

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

result:

ok 118 lines

Test #54:

score: 1
Accepted
time: 2ms
memory: 4072kb

input:

67
17 69 17
9 11
10 13
3 9
5 13
3 5
2 15
7 17
2 4
2 11
2 13
7 15
9 10
3 4
13 17
1 4
1 11
2 5
9 13
5 15
1 5
7 9
4 10
9 15
4 9
10 11
11 15
10 15
4 15
11 17
6 12
2 10
1 9
3 11
1 10
12 16
3 13
2 3
10 17
4 7
4 17
5 7
3 7
3 15
1 7
5 9
6 16
2 9
7 11
7 13
4 13
4 5
5 11
7 10
5 17
3 10
1 15
1 13
1 2
4 11
3 17...

output:

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

result:

ok 114 lines

Test #55:

score: 1
Accepted
time: 4ms
memory: 4064kb

input:

71
10 18 29
4 6
4 6
2 9
3 7
2 9
5 10
4 6
8 10
1 2
3 7
8 10
2 9
1 2
5 10
1 2
5 10
3 7
8 10
10 18 30
6 7
1 9
2 10
2 10
5 9
3 9
4 7
3 9
5 9
4 7
6 7
4 7
3 9
6 7
1 9
2 10
1 9
5 9
16 27 5
2 16
12 14
8 10
8 10
3 15
4 16
5 13
2 16
7 15
9 11
8 10
5 13
4 16
1 16
1 16
4 16
5 13
9 11
3 15
12 14
2 16
12 14
7 15
...

output:

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

result:

ok 134 lines

Test #56:

score: 1
Accepted
time: 3ms
memory: 3808kb

input:

67
10 21 28
2 10
2 10
6 8
5 7
1 4
9 10
7 8
2 10
7 10
5 7
6 8
7 10
7 8
7 8
1 4
1 4
9 10
9 10
6 8
7 10
5 7
17 39 2
6 14
5 12
9 15
1 15
5 12
10 11
6 10
3 7
5 17
6 13
10 11
5 16
4 6
3 7
5 7
4 6
5 7
5 7
6 10
9 15
5 17
5 17
6 14
1 15
6 13
10 11
6 10
3 7
4 6
8 15
8 15
1 15
6 14
8 15
5 16
5 16
5 12
9 15
6 1...

output:

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

result:

ok 127 lines

Test #57:

score: 1
Accepted
time: 3ms
memory: 3776kb

input:

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

output:

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

result:

ok 132 lines

Subtask #6:

score: 0
Time Limit Exceeded

Test #58:

score: 1
Accepted
time: 14ms
memory: 3780kb

input:

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

output:

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

result:

ok 64 lines

Test #59:

score: 1
Accepted
time: 13ms
memory: 3808kb

input:

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

output:

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

result:

ok 68 lines

Test #60:

score: 1
Accepted
time: 16ms
memory: 3780kb

input:

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

output:

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

result:

ok 64 lines

Test #61:

score: 1
Accepted
time: 12ms
memory: 4036kb

input:

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

output:

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

result:

ok 66 lines

Test #62:

score: 1
Accepted
time: 13ms
memory: 3772kb

input:

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

output:

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

result:

ok 64 lines

Test #63:

score: 1
Accepted
time: 9ms
memory: 4132kb

input:

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

output:

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

result:

ok 58 lines

Test #64:

score: 0
Time Limit Exceeded

input:

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

output:


result:


Subtask #7:

score: 0
Time Limit Exceeded

Test #78:

score: 1
Accepted
time: 10ms
memory: 3780kb

input:

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

output:

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

result:

ok 72 lines

Test #79:

score: 1
Accepted
time: 8ms
memory: 3772kb

input:

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

output:

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

result:

ok 68 lines

Test #80:

score: 1
Accepted
time: 13ms
memory: 3772kb

input:

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

output:

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

result:

ok 64 lines

Test #81:

score: 1
Accepted
time: 7ms
memory: 4068kb

input:

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

output:

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

result:

ok 72 lines

Test #82:

score: 1
Accepted
time: 14ms
memory: 3836kb

input:

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

output:

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

result:

ok 64 lines

Test #83:

score: 1
Accepted
time: 14ms
memory: 3720kb

input:

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

output:

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

result:

ok 64 lines

Test #84:

score: 0
Time Limit Exceeded

input:

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

output:


result:


Subtask #8:

score: 0
Time Limit Exceeded

Test #97:

score: 0
Time Limit Exceeded

input:

1
1000 3000 30
82 508
127 347
370 658
350 586
486 863
28 99
293 422
427 710
731 936
555 856
91 374
133 676
351 806
780 992
132 686
73 813
212 971
161 919
402 666
59 106
682 766
288 570
199 882
332 428
633 693
306 694
319 882
356 582
546 916
305 665
336 534
608 901
222 228
422 860
406 869
457 524
114...

output:


result:


Subtask #9:

score: 0
Time Limit Exceeded

Test #109:

score: 0
Time Limit Exceeded

input:

1
1000 3000 30
126 407
55 812
361 478
617 796
500 641
338 450
587 739
1 159
753 795
521 995
313 981
35 595
364 914
334 672
615 802
466 789
262 852
258 867
475 686
543 902
334 795
470 899
146 823
713 850
305 574
201 332
119 298
387 747
187 999
95 981
349 731
749 883
829 895
380 818
568 856
738 981
69...

output:


result:


Subtask #10:

score: 0
Time Limit Exceeded

Test #121:

score: 0
Time Limit Exceeded

input:

1
1000 3000 30
530 695
780 873
245 704
66 567
435 786
5 536
743 895
374 505
283 773
10 50
250 840
100 416
321 704
390 1000
786 921
374 549
490 626
362 759
661 929
589 704
390 446
123 725
371 447
380 930
10 106
661 876
615 695
410 695
421 695
390 561
10 209
338 780
18 345
41 123
121 773
345 384
558 9...

output:


result: