/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/

#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define i64 long long
#define pb push_back
#define ff first
#define ss second
#define isz(x) (int)x.size()
using namespace std;

const int mxN = 2e5 + 5;
const int mod = 1e9 + 7;
const i64 oo = 1e18;

queue<int> q;
bool vis[mxN];
int sz[mxN], dis[mxN], tot_sz;
vector<int> G[mxN], cdis[mxN];

void get_sz(int v, int p) {
    sz[v] = 1;
    for (int u : G[v]) {
        if (vis[u] || u == p) continue;
        get_sz(u, v); sz[v] += sz[u];
    }
}

int find_cen(int v, int p) {
    for (int u : G[v]) {
        if (u == p || vis[u]) continue;
        if (sz[u] > (tot_sz >> 1)) return find_cen(u, v);
    }
    return v;
}

vector< pair<int, int> > encode_map(int N, int K, int &X, vector< pair<int, int> > E) {
    for (auto [u, v] : E) {
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }
    
    get_sz(1, 0);
    tot_sz = find_cen(1, 0);
    X = find_cen(1, 0);

    memset(dis, -1, sizeof dis);
    q.emplace(X); dis[X] = 0;
    while (not q.empty()) {
        int v = q.front(); q.pop();
        cdis[dis[v]].emplace_back(v);
        for (int u : G[v]) if (dis[u] == -1) {
            dis[u] = dis[v] + 1;
            q.emplace(u);
        }
    }

    vector<pair<int, int>> res;
    for (int i = 1; i <= N; ++i) {
        int sz = isz(cdis[i]);
        for (int j = 0; j < sz; ++j) for (int k = j + 1; k < sz; ++k) {
            if (K) {
                --K;
                res.emplace_back(cdis[i][j], cdis[i][k]);
            }
        }
    }
    assert(K == 0);
    return res;
}

vector< pair<int, int> > decode_map(int N, int K, int X, vector< pair<int, int> > E) {
    map<pair<int, int>, int> mp;

    for (auto [u, v] : E) {
        G[u].emplace_back(v);
        G[v].emplace_back(u);
        mp[{u, v}]++;
    }

    memset(dis, -1, sizeof dis);
    q.emplace(X); dis[X] = 0;
    while (not q.empty()) {
        int v = q.front(); q.pop();
        cdis[dis[v]].emplace_back(v);
        for (int u : G[v]) if (dis[u] != -1) {
            dis[u] = dis[v] + 1;
            q.emplace(u);
        }
    }

    for (int i = 1; i <= N; ++i) {
        int sz = isz(cdis[i]);
        for (int j = 0; j < sz; ++j) for (int k = j + 1; k < sz; ++k) {
            if (mp.count({cdis[i][j], cdis[i][k]})) mp.erase({cdis[i][j], cdis[i][k]});
            if (mp.count({cdis[i][k], cdis[i][j]})) mp.erase({cdis[i][k], cdis[i][j]});
        }
    }

    vector<pair<int, int>> res;
    for (auto [tmp, _] : mp) res.push_back(tmp);
    return res;
}

// int main() {
//     int X;
//     auto res = encode_map(6, 2, X, {{1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 6}});
//     cout << X << endl;
//     for (auto [u, v] : res) cout << u << ", " << v << endl;
// }