#include <bits/stdc++.h>
using namespace std;

using ii = pair<int, int>;

vector<vector<int>> build_adj(int N, const vector<ii> &E){
	vector<vector<int>> adj(N);
	for (auto [x, y]: E){
		adj[x-1].push_back(y-1);
		adj[y-1].push_back(x-1);
	}
	return adj;
}

vector<int> bfs(int N, int K, int root, const vector<vector<int>> &adj){
	vector<int> layer(N, N);
	queue<int> q;
	layer[root] = 0; q.push(root);

	while (!q.empty()){
		int x = q.front(); q.pop();
		for (auto k: adj[x]){
			if (layer[k] == N){
				layer[k] = layer[x] + 1;
				q.push(k);
			}
		}
	}

	vector<int> cnt(N+1, 0);
	long long res = 0;
	for (int i = 0; i < N; i++) res += (cnt[layer[i]]++);
	if (res >= K) return layer;
	return {};
}

vector<ii> encode_map(int N, int K, int &X, vector<ii> E){
	auto adj = build_adj(N, E);

	vector<ii> result = E;

	for (int i = 0; i < N; i++){
		auto layer = bfs(N, K, i, adj);
		if (layer.empty()) continue;

		vector<vector<int>> v(N + 1);
		for (int j = 0; j < N; j++){
			v[layer[j]].push_back(j);
		}

		for (int c = 0; c < N; c++){
			if (!K) break;
			for (int idx1 = 0; idx1 < (int)v[c].size(); idx1++){
				if (!K) break;
				for (int idx2 = idx1 + 1; idx2 < (int)v[c].size(); idx2++){
					if (!K) break;
					K--;
					result.emplace_back(v[c][idx1] + 1, v[c][idx2] + 1);
				}
			}
		}

		X = i+1;
		break;
	}

	return result;
}

vector<ii> decode_map(int N, int K, int X, vector<ii> E){
	auto adj = build_adj(N, E);

	auto layer = bfs(N, K, X-1, adj);
	vector<ii> result;

	for (auto [x, y]: E){
		if (layer[x-1] != layer[y-1]) result.emplace_back(x, y);
	}

	return result;
}