QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#429718#5239. Mędrcy [A]iee9 4505ms7488kbC++173.9kb2024-06-02 19:35:212024-06-02 19:35:21

Judging History

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

  • [2024-06-02 19:35:21]
  • 评测
  • 测评结果:9
  • 用时:4505ms
  • 内存:7488kb
  • [2024-06-02 19:35:21]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
template<class T>
using oset = set<T>;
#define set unordered_set
struct DSU {
	int n;
	vector<int> p, edge;
	DSU(int _n) : n(_n), p(_n), edge(_n) {
		iota(p.begin(), p.end(), 0);
	}
	int get(int u) {
		return p[u] == u ? u : p[u] = get(p[u]);
	}
	void unite(int u, int v) {
		int fu = get(u), fv = get(v);
		if (fu == fv) {
			edge[fu]++;
		} else {
			p[fu] = fv;
			edge[fv] += edge[fu] + 1;
		}
	}
	vector<vector<int>> groups() {
		vector<vector<int>> nl(n), res;
		for (int i = 0; i < n; i++) {
			nl[get(i)].push_back(i);
		}
		for (int i = 0; i < n; i++) {
			if (p[i] == i) {
				res.push_back(nl[i]);
			}
		}
		return res;
	}
};
void solve() {
	int n, m, k;
	cin >> n >> m >> k;
	oset<pair<int, int>> s;
	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		if (u > v) swap(u, v);
		s.insert({u, v});
	}
	vector<set<int>> e(n);
	for (auto [u, v] : s) {
		e[u].insert(v);
		e[v].insert(u);
	}
	int maxs = -1;
	vector<int> inans(n);
	function<void(const set<int>&, const set<int>&, int, int, const set<int>&)> dfs = 
	[&](const set<int> &nodes, const set<int> &cand, int curk, int siz, const set<int> &must) {
		if (curk < 0) return;
		if (siz > maxs) {
			maxs = siz;
			fill(inans.begin(), inans.end(), 0);
		}
		if (siz >= maxs) {
			vector<int> inset(n);
			for (int u : must) {
				inset[u] = 1;
			}
			for (int i = 0; i < n; i++) {
				if (!inset[i]) {
					inans[i] = 1;
				}
			}
		}
		if (cand.empty()) return;
		int mx = -1, mxu = -1;
		vector<vector<int>> cg(n);
		for (int u : cand) {
			int deg = 0;
			for (int v : e[u]) {
				if (cand.count(v)) {
					deg++;
					cg[u].push_back(v);
				}
			}
			if (deg >= mx) {
				mx = deg;
				mxu = u;
			}
		}
		if (mx >= 3) {
			vector<int> vs;
			for (int v : e[mxu]) {
				if (cand.count(v)) {
					vs.push_back(v);
				}
			}
			{
				auto _nodes = nodes;
				auto _cand = cand;
				_nodes.insert(mxu);
				for (int v : vs) {
					_cand.erase(v);
				}
				_cand.erase(mxu);
				dfs(_nodes, _cand, curk - mx, _nodes.size(), _nodes);
			}
			{
				auto _cand = cand;
				_cand.erase(mxu);
				dfs(nodes, _cand, curk - 1, nodes.size(), nodes);
			}
		} else {
			DSU d(n);
			for (int u : cand) {
				for (int v : cg[u]) {
					if (u < v) d.unite(u, v);
				}
			}
			auto groups = d.groups();
			int Siz = siz, sum = 0;
			set<int> _must = nodes;
			for (const auto &vec : groups) {
				if (!cand.count(vec[0])) continue;
				sum += vec.size();
				int edge = d.edge[d.get(vec[0])];
				assert(edge == vec.size() - 1 || edge == vec.size());
				int S = -1, mn = 3;
				for (int u : vec) {
					if (cg[u].size() < mn) {
						mn = cg[u].size();
						S = u;
					}
				}
				vector<int> vis(n);
				vector<int> seq;
				function<void(int)> rec = [&](int u) {
					if (vis[u]) return;
					seq.push_back(u);
					vis[u] = 1;
					for (int v : cg[u]) {
						rec(v);
					}
				};
				rec(S);
				if (edge == vec.size()) {
					Siz += vec.size() / 2;
				} else {
					Siz += (vec.size() + 1) / 2;
					if (vec.size() % 2) {
						assert(seq.size() == vec.size());
						for (int i = 0; i < seq.size(); i += 2) {
							_must.insert(seq[i]);
						}
					}
				}
			}
			dfs({}, {}, curk - (sum - Siz), Siz, _must);
		}
	};
	set<int> all;
	for (int i = 0; i < n; i++) {
		all.insert(i);
	}
	dfs({}, all, k, 0, {});
	if (maxs == -1 || n - maxs > k) {
		cout << -1 << "\n";
	} else {
		cout << n - maxs << " ";
		vector<int> nodes;
		for (int i = 0; i < n; i++) {
			if (inans[i]) {
				nodes.push_back(i);
			}
		}
		cout << nodes.size() << "\n";
		for (int i = 0; i < nodes.size(); i++) {
			cout << nodes[i] + 1 << " \n"[i + 1 == nodes.size()];
		}
	}
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	int t;
	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}

詳細信息

Subtask #1:

score: 1
Accepted

Test #1:

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

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

result:

ok 243 lines

Test #2:

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

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

result:

ok 237 lines

Test #3:

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

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

result:

ok 256 lines

Test #4:

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

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

result:

ok 270 lines

Test #5:

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

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

result:

ok 251 lines

Test #6:

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

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

result:

ok 229 lines

Test #7:

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

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

result:

ok 232 lines

Test #8:

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

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

result:

ok 230 lines

Test #9:

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

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

result:

ok 259 lines

Test #10:

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

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

result:

ok 246 lines

Test #11:

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

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

result:

ok 253 lines

Test #12:

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

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

result:

ok 646 lines

Subtask #2:

score: 1
Accepted

Test #13:

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

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

result:

ok 257 lines

Test #14:

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

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
3 6 7 8 9 10 12...

result:

ok 233 lines

Test #15:

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

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

result:

ok 276 lines

Test #16:

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

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

result:

ok 266 lines

Test #17:

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

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

result:

ok 238 lines

Test #18:

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

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 8 9
2 3
1 2 3
...

result:

ok 239 lines

Test #19:

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

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 9 10 11 12
-1
4...

result:

ok 224 lines

Test #20:

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

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

result:

ok 228 lines

Test #21:

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

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

result:

ok 256 lines

Test #22:

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

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

result:

ok 262 lines

Test #23:

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

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

result:

ok 245 lines

Test #24:

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

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 6 7 8 9 10 ...

result:

ok 129 lines

Subtask #3:

score: 1
Accepted

Test #25:

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

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 10 11 12...

result:

ok 132 lines

Test #26:

score: 1
Accepted
time: 5ms
memory: 3668kb

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 9 11 12...

result:

ok 126 lines

Test #27:

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

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 7 8 9 10 1...

result:

ok 132 lines

Test #28:

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

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 15
2 3 4 6 7...

result:

ok 132 lines

Test #29:

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

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 17 18
...

result:

ok 119 lines

Test #30:

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

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 19
1 2 3...

result:

ok 120 lines

Test #31:

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

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 6 7 8 ...

result:

ok 120 lines

Test #32:

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

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 7 8 9 1...

result:

ok 112 lines

Test #33:

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

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
10 20...

result:

ok 119 lines

Test #34:

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

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 6 7 8 11 1...

result:

ok 117 lines

Test #35:

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

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 4 5 6 ...

result:

ok 140 lines

Subtask #4:

score: 1
Accepted

Test #36:

score: 1
Accepted
time: 4ms
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 9 10
9 14...

result:

ok 134 lines

Test #37:

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

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 17
6 8
1 2...

result:

ok 134 lines

Test #38:

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

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 6 7 8 9 ...

result:

ok 134 lines

Test #39:

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

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 5 6 7 9 10 ...

result:

ok 130 lines

Test #40:

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

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 14 15 16...

result:

ok 123 lines

Test #41:

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

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 11
6 11...

result:

ok 124 lines

Test #42:

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

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 7 8 9 ...

result:

ok 108 lines

Test #43:

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

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 5 6 7 ...

result:

ok 116 lines

Test #44:

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

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
5 5
3 5 7 12 13
6...

result:

ok 122 lines

Test #45:

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

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
1 7 9 11 12...

result:

ok 118 lines

Test #46:

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

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 12 13 14...

result:

ok 128 lines

Subtask #5:

score: 1
Accepted

Test #47:

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

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 11 15 16 ...

result:

ok 128 lines

Test #48:

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

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

result:

ok 138 lines

Test #49:

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

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 13 14 15 1...

result:

ok 130 lines

Test #50:

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

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
10 15
1 2 ...

result:

ok 128 lines

Test #51:

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

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 8 9 10...

result:

ok 116 lines

Test #52:

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

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
6 11
1...

result:

ok 128 lines

Test #53:

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

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 11 12 1...

result:

ok 118 lines

Test #54:

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

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 18
1 2...

result:

ok 114 lines

Test #55:

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

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
3 3
3 9 1...

result:

ok 134 lines

Test #56:

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

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

result:

ok 127 lines

Test #57:

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

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 4 5 7 8...

result:

ok 132 lines

Subtask #6:

score: 1
Accepted

Test #58:

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

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 33
1 2...

result:

ok 64 lines

Test #59:

score: 1
Accepted
time: 27ms
memory: 4012kb

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 3 4 8...

result:

ok 68 lines

Test #60:

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

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 16 1...

result:

ok 64 lines

Test #61:

score: 1
Accepted
time: 27ms
memory: 3828kb

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 40
...

result:

ok 66 lines

Test #62:

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

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
17 ...

result:

ok 64 lines

Test #63:

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

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 20 ...

result:

ok 58 lines

Test #64:

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

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:

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

result:

ok 39 lines

Test #65:

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

input:

26
43 129 28
9 19
20 30
16 42
9 12
3 13
37 43
10 39
18 40
12 20
11 26
6 36
2 15
11 34
33 41
36 38
11 26
10 39
6 32
26 29
16 42
2 15
35 37
1 43
4 15
1 43
7 10
17 23
2 4
16 42
9 19
6 32
18 25
14 33
17 23
11 26
26 29
7 10
6 36
9 12
19 30
7 10
36 38
20 30
37 43
21 39
11 34
3 13
14 41
2 4
10 39
33 41
12 ...

output:

25 43
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 41 42 43
-1
14 26
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
-1
17 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 29 30
-1
-1
...

result:

ok 34 lines

Test #66:

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

input:

27
49 120 17
3 41
27 28
3 49
2 18
27 39
13 21
36 47
6 41
7 16
32 34
36 47
1 25
3 41
3 41
10 20
30 31
30 31
17 19
29 34
2 22
11 24
35 42
32 34
10 44
32 34
13 30
13 30
2 22
19 36
1 14
23 37
13 21
29 34
11 32
10 44
23 28
17 48
20 42
27 39
16 29
6 41
4 25
36 47
13 21
12 31
1 14
2 22
11 24
8 39
23 37
19 ...

output:

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

result:

ok 42 lines

Test #67:

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

input:

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

output:

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

result:

ok 33 lines

Test #68:

score: 1
Accepted
time: 394ms
memory: 4056kb

input:

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

output:

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

result:

ok 30 lines

Test #69:

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

input:

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

output:

-1

result:

ok single line: '-1'

Test #70:

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

input:

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

output:

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

result:

ok 25 lines

Test #71:

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

input:

16
60 147 8
29 56
9 24
9 24
9 19
9 24
18 39
1 4
16 43
7 47
16 22
36 40
48 54
46 49
32 52
44 56
16 22
36 38
3 28
31 52
15 58
9 50
1 59
18 39
33 37
18 55
51 56
23 60
27 42
9 19
13 36
18 55
23 60
33 56
23 52
29 56
8 27
3 28
3 47
27 42
23 60
1 4
25 31
6 29
13 36
3 28
26 34
15 58
4 32
36 40
23 52
20 27
1...

output:

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

result:

ok 19 lines

Test #72:

score: 1
Accepted
time: 20ms
memory: 3756kb

input:

16
60 153 11
11 48
34 57
3 27
13 42
15 19
1 50
1 32
9 45
25 40
24 57
3 35
13 42
17 21
1 50
9 45
25 36
4 13
14 35
9 13
49 51
16 21
1 57
1 28
52 56
1 28
17 35
29 55
27 29
43 58
9 23
44 49
34 57
9 23
16 21
1 26
13 41
52 56
15 19
19 37
5 33
49 51
3 5
12 50
29 55
17 21
6 35
11 48
1 26
3 35
30 52
13 41
1 ...

output:

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

result:

ok 20 lines

Test #73:

score: 1
Accepted
time: 3404ms
memory: 3744kb

input:

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

output:

27 54
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 41 42 43 44 45 46 47 48 49 50 51 52 53 54
25 50
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 41 42 43 44 45 46 47 48 ...

result:

ok 36 lines

Test #74:

score: 1
Accepted
time: 1346ms
memory: 3824kb

input:

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

output:

29 58
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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58
28 28
2 3 4 5 6 7 9 10 15 17 18 24 26 29 30 31 32 33 37 38 40 41 42 43 47 49 51 52
27 54
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1...

result:

ok 36 lines

Test #75:

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

input:

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

output:

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

result:

ok 25 lines

Test #76:

score: 1
Accepted
time: 5ms
memory: 3680kb

input:

18
59 161 30
2 52
2 29
30 36
2 13
8 30
29 55
17 26
18 48
18 45
2 30
30 34
36 43
29 34
30 59
21 45
32 52
30 56
15 30
12 18
7 49
12 30
29 34
5 56
34 52
34 45
37 45
34 45
30 48
12 30
34 56
7 24
30 43
34 45
14 56
15 45
18 30
18 56
30 49
25 30
18 45
8 30
30 34
4 30
30 57
34 45
5 17
25 30
18 30
30 43
5 47...

output:

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

result:

ok 36 lines

Test #77:

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

input:

17
57 178 30
18 44
2 47
17 56
15 32
42 50
42 50
14 50
26 50
14 33
18 50
50 52
14 17
7 47
15 17
14 41
14 15
2 14
26 42
22 50
14 21
14 17
14 17
14 47
13 14
22 32
18 22
17 22
14 39
34 42
20 21
41 50
14 50
14 21
34 41
47 50
14 47
24 50
27 55
14 54
32 50
50 56
14 54
32 41
14 15
42 50
14 17
14 18
18 34
13...

output:

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

result:

ok 34 lines

Subtask #7:

score: 1
Accepted

Test #78:

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

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 7 8 ...

result:

ok 72 lines

Test #79:

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

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 13 1...

result:

ok 68 lines

Test #80:

score: 1
Accepted
time: 28ms
memory: 3844kb

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 29 ...

result:

ok 64 lines

Test #81:

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

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 10 11...

result:

ok 72 lines

Test #82:

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

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 8 9 ...

result:

ok 64 lines

Test #83:

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

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 12 ...

result:

ok 64 lines

Test #84:

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

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:

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

result:

ok 42 lines

Test #85:

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

input:

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

output:

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

result:

ok 44 lines

Test #86:

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

input:

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

output:

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

result:

ok 23 lines

Test #87:

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

input:

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

output:

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

result:

ok 30 lines

Test #88:

score: 1
Accepted
time: 124ms
memory: 3816kb

input:

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

output:

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

result:

ok 30 lines

Test #89:

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

input:

3
60 812 30
5 14
40 47
30 49
11 36
25 45
48 58
15 46
11 37
16 47
28 50
10 16
10 56
24 29
8 20
24 57
4 44
14 48
9 33
12 30
16 59
31 41
14 34
4 20
2 24
1 24
48 59
10 45
16 27
10 38
31 39
39 55
8 39
4 55
15 21
15 38
7 27
15 25
4 28
18 39
41 55
25 53
3 31
37 39
2 41
40 53
5 42
39 41
37 50
18 49
34 46
13...

output:

-1
-1
-1

result:

ok 3 lines

Test #90:

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

input:

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

output:

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

result:

ok 21 lines

Test #91:

score: 1
Accepted
time: 26ms
memory: 3984kb

input:

16
60 153 12
32 54
14 22
10 59
6 27
29 53
17 25
14 22
10 46
38 56
38 39
6 57
38 56
7 9
44 48
24 54
6 31
24 40
17 38
20 44
34 43
24 40
54 58
7 36
2 12
42 51
22 44
6 57
34 56
7 36
16 42
44 48
23 54
6 30
26 58
6 31
54 58
44 53
54 59
24 54
32 54
9 37
9 37
4 50
16 41
11 38
11 38
17 38
16 42
31 49
12 54
1...

output:

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

result:

ok 22 lines

Test #92:

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

input:

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

output:

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

result:

ok 21 lines

Test #93:

score: 1
Accepted
time: 2988ms
memory: 4100kb

input:

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

output:

28 28
1 2 3 7 8 12 13 14 15 16 22 24 25 27 28 29 35 37 38 40 43 45 46 47 49 53 54 55
27 54
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 41 42 43 44 45 46 47 48 49 50 51 52 53 54
27 27
1 3 4 5 6 7 9 10 11 12 14 16 17 20 22 23 24 26 29 ...

result:

ok 36 lines

Test #94:

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

input:

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

output:

30 60
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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
29 58
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 41 42 ...

result:

ok 36 lines

Test #95:

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

input:

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

output:

30 30
1 2 5 7 8 9 10 14 15 16 17 18 19 20 25 29 30 32 33 34 35 36 38 40 41 44 50 52 54 55
30 30
1 3 7 8 11 12 13 14 16 17 18 19 22 26 27 28 30 31 32 35 42 43 44 46 48 49 53 56 57 58
30 60
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 4...

result:

ok 36 lines

Test #96:

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

input:

18
58 169 30
19 24
4 7
4 19
25 49
3 10
4 10
10 14
4 56
16 41
10 56
26 31
4 10
25 56
2 56
24 56
26 49
4 25
25 27
26 49
10 13
10 49
19 49
10 11
6 40
31 56
10 27
4 10
4 25
4 21
1 56
10 57
10 12
4 34
4 56
10 19
10 13
10 19
4 10
10 24
10 49
10 12
19 25
10 34
4 34
16 28
10 12
19 42
4 50
4 10
19 51
4 10
1 ...

output:

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

result:

ok 36 lines

Subtask #8:

score: 0
Time Limit Exceeded

Test #97:

score: 1
Accepted
time: 42ms
memory: 7488kb

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:

-1

result:

ok single line: '-1'

Test #98:

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

input:

1
1000 3000 30
266 447
201 576
363 986
110 318
382 520
182 339
5 235
676 781
736 919
396 814
265 779
677 862
67 354
154 603
440 751
642 911
422 642
23 154
110 861
167 400
316 619
778 789
461 668
621 677
339 419
154 248
354 550
398 701
73 940
461 829
547 923
643 986
339 985
110 901
96 461
560 856
552...

output:

30 30
73 110 154 167 178 201 235 265 266 316 339 354 396 398 432 440 461 520 560 565 581 642 677 761 778 781 873 919 923 986

result:

ok 2 lines

Test #99:

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

input:

1
1000 3000 30
644 655
62 723
103 222
738 939
567 903
47 644
281 383
450 498
115 414
487 502
173 383
115 515
596 886
27 712
191 200
392 769
218 940
117 304
86 861
427 511
16 234
77 448
366 870
11 879
113 366
47 502
38 832
712 769
85 147
492 826
448 718
383 670
58 596
686 732
234 943
268 427
610 976
...

output:

30 30
11 38 86 115 117 147 200 218 222 234 366 383 392 427 448 498 502 566 572 596 610 644 712 723 732 738 826 865 895 903

result:

ok 2 lines

Test #100:

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

input:

1
1000 2997 30
345 954
228 863
24 467
652 853
49 389
58 921
144 824
477 947
431 981
349 746
625 915
166 274
443 548
353 756
87 901
31 622
450 672
27 57
518 608
354 825
142 974
40 916
214 798
601 950
155 923
186 830
895 959
270 474
602 798
300 491
20 982
876 935
774 811
91 294
387 965
277 803
47 478
...

output:

-1

result:

ok single line: '-1'

Test #101:

score: 0
Time Limit Exceeded

input:

1
1000 1500 30
18 964
877 952
462 797
179 209
788 895
735 848
196 745
111 781
570 626
424 898
369 575
528 751
493 948
404 890
74 303
419 729
20 764
243 839
46 544
171 803
369 483
165 714
43 103
354 905
145 453
222 280
685 930
235 773
892 972
544 588
329 571
221 796
300 977
125 610
309 976
480 741
73...

output:


result:


Subtask #9:

score: 1
Accepted

Test #109:

score: 1
Accepted
time: 37ms
memory: 7484kb

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:

-1

result:

ok single line: '-1'

Test #110:

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

input:

1
1000 3000 30
534 661
174 197
306 990
51 215
197 622
327 560
503 769
462 503
88 327
150 713
77 876
441 755
150 354
14 974
35 281
441 537
501 766
621 657
309 568
234 854
278 657
115 503
162 501
976 990
121 618
441 814
439 854
447 876
197 509
604 925
632 849
281 382
15 319
211 854
258 281
56 501
296 ...

output:

30 30
14 51 139 150 177 197 281 296 302 309 319 327 338 395 441 501 503 534 593 594 618 632 657 706 854 876 884 891 925 990

result:

ok 2 lines

Test #111:

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

input:

1
1000 3000 30
28 492
748 963
638 861
276 350
314 741
263 425
38 147
23 899
28 310
661 725
128 691
160 622
519 691
28 594
79 659
293 427
76 404
425 725
111 246
300 408
189 691
311 673
263 497
691 888
616 895
246 392
157 748
616 640
147 606
147 866
119 431
350 521
119 208
691 867
883 945
246 984
173 ...

output:

29 29
28 41 79 119 147 246 263 293 314 350 404 408 489 525 587 610 616 622 638 673 688 691 725 748 810 825 899 933 945

result:

ok 2 lines

Test #112:

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

input:

1
1000 3000 30
400 785
352 391
159 261
432 622
156 416
153 767
17 551
89 423
15 247
320 957
114 666
378 851
276 533
151 700
98 445
841 897
840 967
315 379
51 677
162 166
57 130
481 880
251 503
308 703
365 427
193 339
721 730
577 586
67 528
65 251
181 403
104 472
264 920
377 400
395 439
603 902
150 8...

output:

-1

result:

ok single line: '-1'

Test #113:

score: 1
Accepted
time: 4085ms
memory: 7008kb

input:

1
1000 2000 30
706 736
103 344
208 727
115 564
23 627
51 274
151 467
684 732
521 618
669 993
665 893
56 357
426 709
624 666
326 555
167 211
57 767
139 305
37 430
347 640
479 506
531 717
512 642
380 416
266 662
46 144
601 946
291 447
327 862
123 213
493 975
686 767
209 497
95 873
110 252
616 832
129 ...

output:

-1

result:

ok single line: '-1'

Test #114:

score: 1
Accepted
time: 4505ms
memory: 6860kb

input:

1
1000 800 30
379 588
182 956
785 891
58 420
186 597
41 935
543 845
264 615
211 973
30 217
516 632
376 414
305 337
666 960
19 35
354 679
413 597
32 812
182 940
335 591
125 653
370 851
627 645
268 854
323 824
12 708
411 648
90 734
292 894
609 981
89 584
154 753
663 963
617 860
636 767
25 991
829 984
...

output:

-1

result:

ok single line: '-1'

Test #115:

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

input:

10
103 315 30
28 70
2 15
12 62
37 72
15 44
74 103
18 80
15 49
2 80
5 74
2 74
2 74
44 58
21 99
74 99
37 66
2 44
2 58
44 74
15 58
44 74
12 74
74 99
10 15
12 74
2 74
35 80
15 44
15 49
33 95
89 101
15 35
54 55
44 47
44 74
2 46
74 80
10 74
15 82
20 56
47 74
58 74
9 74
74 100
54 74
5 74
13 74
66 74
54 80
...

output:

30 37
2 10 12 13 14 15 18 20 21 28 33 35 37 38 40 43 44 47 48 54 57 58 61 62 63 64 72 74 76 80 82 89 90 91 95 99 101
26 30
5 8 13 15 16 21 23 27 29 36 37 46 49 50 57 62 65 66 68 71 77 80 81 82 83 88 90 92 93 94
26 32
1 6 16 17 18 22 23 24 25 30 33 38 41 45 46 47 52 57 58 59 60 63 64 68 69 73 74 77 8...

result:

ok 19 lines

Test #116:

score: 1
Accepted
time: 52ms
memory: 3828kb

input:

10
108 316 30
26 61
21 96
60 93
1 61
1 49
14 50
50 105
75 97
44 64
50 52
44 99
96 104
44 50
16 44
13 104
45 62
36 75
57 102
44 50
50 107
44 61
44 50
30 32
8 60
44 63
44 65
40 44
1 50
71 104
50 63
50 65
49 50
73 82
16 72
75 100
40 50
25 101
1 50
1 50
8 107
1 50
41 61
61 66
10 50
65 97
44 61
50 100
50...

output:

-1
29 40
7 9 12 16 19 21 22 23 26 28 29 31 35 39 47 53 55 58 59 63 64 65 66 68 72 74 75 76 79 80 82 88 90 92 95 98 99 100 102 106
27 38
6 7 9 16 21 28 29 30 32 34 36 38 39 41 42 45 47 48 51 53 54 56 57 59 62 63 65 66 67 70 76 77 78 85 86 90 91 94
25 34
5 6 10 11 14 15 20 22 29 30 32 46 48 50 52 53 5...

result:

ok 19 lines

Test #117:

score: 1
Accepted
time: 3402ms
memory: 3880kb

input:

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

output:

29 29
2 3 5 6 9 10 12 15 16 18 19 21 29 30 33 34 36 38 39 40 43 45 46 47 48 51 52 53 55
30 60
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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
28 28
3 4 6 7 8 9 13 15 16 17 18 21...

result:

ok 34 lines

Test #118:

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

input:

11
89 192 30
37 87
8 31
58 77
32 88
6 42
7 25
38 80
58 77
18 75
75 79
7 47
38 80
18 75
30 51
32 88
43 68
29 42
41 64
29 42
60 67
54 89
52 64
69 73
5 49
3 59
7 47
40 83
20 57
12 85
32 88
29 42
16 88
7 25
12 85
56 72
56 72
3 59
34 81
53 82
44 85
19 71
2 40
75 79
19 71
3 24
41 64
58 77
60 67
7 25
7 47
...

output:

-1
30 46
1 2 5 6 11 12 14 15 16 18 22 23 25 26 27 30 31 32 35 38 44 45 46 48 49 51 53 54 56 60 64 65 68 69 70 71 72 74 78 80 82 84 85 87 88 89
30 47
1 2 3 5 6 8 9 11 12 13 15 16 17 21 22 23 24 25 27 29 34 35 36 40 45 48 50 52 54 55 57 58 59 60 64 65 66 69 72 76 77 78 79 82 84 85 87
28 41
2 3 5 6 11 ...

result:

ok 19 lines

Test #119:

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

input:

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

output:

30 60
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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
29 29
1 2 6 7 8 9 11 12 13 16 18 22 24 26 27 29 32 35 39 40 42 46 47 48 52 54 56 57 58
29 29
1 5 7 8 13 14 15 17 22 23 25 2...

result:

ok 32 lines

Test #120:

score: 1
Accepted
time: 983ms
memory: 6820kb

input:

1
1000 2997 30
294 473
281 803
180 740
190 333
14 331
768 896
378 944
272 943
338 388
529 793
461 966
823 986
76 703
167 838
152 328
42 61
107 431
439 917
420 513
186 671
32 660
241 268
193 398
82 451
177 574
254 627
540 928
411 550
41 748
356 849
355 950
124 257
295 521
399 585
2 609
149 330
504 95...

output:

-1

result:

ok single line: '-1'

Subtask #10:

score: 1
Accepted

Test #121:

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

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:

29 29
5 10 66 123 250 345 352 368 374 390 416 447 462 622 626 647 661 691 695 704 714 743 759 773 780 786 853 922 930

result:

ok 2 lines

Test #122:

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

input:

1
1000 3000 30
79 286
325 945
25 566
629 751
523 566
398 742
769 793
622 706
91 484
287 880
321 966
436 966
119 618
243 349
119 894
398 692
249 287
444 733
400 831
815 902
155 693
356 597
455 966
22 119
486 597
232 444
482 878
91 467
461 831
605 894
39 966
598 966
287 592
243 722
170 398
392 831
383...

output:

30 30
91 119 128 155 158 223 243 277 286 287 325 332 368 398 444 461 482 566 594 597 622 629 682 761 793 815 831 894 919 966

result:

ok 2 lines

Test #123:

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

input:

1
1000 3000 30
69 502
36 140
484 840
882 978
399 605
79 902
566 615
486 675
54 768
367 671
532 762
886 972
882 978
158 255
903 943
16 607
46 548
60 555
133 226
240 704
172 341
543 714
261 855
482 664
541 632
22 47
23 520
242 471
411 947
387 440
460 510
197 290
617 881
64 890
784 793
507 709
679 686
...

output:

-1

result:

ok single line: '-1'

Test #124:

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

input:

1
1000 999 30
658 792
12 345
663 977
286 866
424 606
210 876
285 859
29 537
242 687
475 498
440 690
159 689
150 663
369 856
34 382
16 20
87 518
71 485
353 532
104 515
259 479
7 101
86 171
710 982
90 312
125 895
623 867
704 774
618 682
104 399
529 702
221 740
364 814
272 517
199 844
274 437
572 754
4...

output:

-1

result:

ok single line: '-1'

Test #125:

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

input:

1
1000 666 30
91 706
198 897
145 973
151 544
437 750
817 944
723 759
770 991
413 993
352 776
170 483
332 612
498 852
552 671
43 465
278 668
537 808
583 774
814 1000
321 614
71 651
110 167
213 399
361 980
351 641
264 524
346 480
810 924
357 845
240 950
314 581
758 882
458 764
11 194
232 948
60 630
64...

output:

-1

result:

ok single line: '-1'

Test #126:

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

input:

1
1000 3000 30
710 833
132 710
518 710
637 710
412 710
710 777
303 710
32 710
337 710
693 710
510 710
547 710
83 710
373 710
61 710
326 710
238 710
386 710
83 710
710 718
49 710
710 949
466 710
151 710
191 710
710 813
710 915
541 710
710 748
569 710
710 876
211 710
710 818
417 710
365 710
592 710
71...

output:

1 1
710

result:

ok 2 lines

Test #127:

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

input:

9
99 284 30
31 43
12 31
12 33
43 96
31 61
52 89
31 43
31 67
31 43
34 76
31 34
8 44
7 89
67 88
31 43
31 46
31 34
25 39
43 46
34 88
22 62
9 67
31 50
34 70
52 89
31 73
67 78
43 63
37 43
43 89
7 88
52 86
43 67
31 45
31 61
38 70
31 88
9 43
31 52
52 87
31 34
1 43
31 52
40 67
34 76
31 52
43 93
31 70
52 88
...

output:

24 34
1 4 5 7 8 9 12 14 15 20 22 26 31 34 39 42 43 44 50 51 52 61 67 70 73 77 85 87 88 89 94 96 98 99
26 35
1 6 8 9 11 14 20 21 26 27 29 33 39 48 50 51 53 54 55 56 61 64 65 67 68 71 72 76 82 86 87 89 90 91 92
-1
27 39
5 10 12 19 20 22 26 27 28 31 33 35 36 40 42 49 51 54 55 57 59 61 64 65 67 68 69 70...

result:

ok 15 lines

Test #128:

score: 1
Accepted
time: 31ms
memory: 3884kb

input:

9
104 262 30
80 103
9 57
38 56
77 93
47 57
44 77
52 93
77 78
38 102
34 38
28 77
37 75
35 38
47 77
38 77
18 77
77 97
57 103
56 84
57 96
22 52
57 77
55 77
9 57
57 77
26 77
36 74
57 77
35 102
12 57
75 80
78 100
38 57
32 52
38 57
38 52
30 38
52 68
52 77
9 57
18 38
56 77
32 77
31 57
38 74
1 77
29 38
19 5...

output:

26 36
6 9 18 19 25 30 32 35 36 37 38 41 44 47 48 49 51 52 54 55 56 57 68 74 75 77 78 79 80 84 85 87 90 93 100 103
28 40
5 6 7 9 11 12 15 21 22 25 28 32 34 36 37 40 41 44 52 53 54 56 59 61 62 64 67 70 74 75 77 82 89 90 92 93 95 96 97 99
-1
27 41
2 3 4 5 6 8 13 16 17 18 24 34 36 37 38 40 41 43 44 45 5...

result:

ok 16 lines

Test #129:

score: 1
Accepted
time: 1270ms
memory: 3824kb

input:

17
60 150 30
5 7
13 45
15 29
24 59
53 55
13 35
1 24
2 35
59 60
3 23
29 52
10 34
34 46
2 53
45 47
15 49
21 23
12 20
36 53
38 56
1 51
17 22
10 48
11 21
32 43
28 55
3 56
22 25
43 56
13 40
14 47
41 58
32 53
46 48
11 44
3 13
22 44
17 29
25 58
29 44
6 14
15 36
15 34
11 28
14 39
42 60
19 43
26 38
20 51
31 ...

output:

30 60
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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
29 29
1 3 5 6 10 11 12 13 14 15 16 21 22 24 25 26 27 30 31 35 37 38 40 43 47 48 49 52 53
29 29
1 2 3 4 5 6 10 12 13 18 22 2...

result:

ok 34 lines

Test #130:

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

input:

16
60 138 30
5 58
8 25
7 33
4 34
5 58
37 53
3 49
11 56
8 25
30 32
42 54
5 58
17 46
3 49
9 45
10 18
8 25
22 40
31 47
11 56
22 40
43 59
42 54
15 51
5 58
13 38
42 54
31 47
17 46
5 58
3 49
17 46
7 33
10 18
26 52
31 47
8 25
3 49
11 56
42 54
6 55
31 47
10 18
17 46
16 60
13 38
43 59
37 53
6 55
15 51
14 29
...

output:

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

result:

ok 32 lines

Test #131:

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

input:

16
60 153 30
47 56
19 29
8 56
50 57
19 20
4 39
21 32
11 18
18 34
8 26
8 26
4 39
1 28
10 29
3 34
23 33
40 58
1 28
23 33
19 29
20 44
47 48
4 7
5 31
9 36
10 29
53 54
23 24
23 24
12 52
18 34
7 55
6 48
12 14
16 44
25 31
21 55
9 36
25 45
47 48
11 14
12 14
18 34
11 14
19 29
3 34
16 33
1 28
4 39
27 37
11 18...

output:

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

result:

ok 32 lines

Test #132:

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

input:

1
1000 2997 30
94 656
406 968
143 209
365 664
188 867
174 658
305 626
144 213
38 614
323 594
112 458
141 287
353 750
35 300
320 854
547 873
367 811
171 383
324 719
1 308
322 496
458 935
119 170
389 555
696 837
401 471
564 757
313 982
246 877
742 844
62 94
463 545
662 787
48 500
400 943
425 962
131 4...

output:

-1

result:

ok single line: '-1'