# include <bits/stdc++.h>
# include "jngen/jngen.h"
using namespace std;
mt19937 rng(42);
const int MAXN = 1e5 + 10;
int N, Q;
set <int> g[MAXN];
vector <pair<int, int>> edges;
int depth[MAXN], par[MAXN], subs[MAXN], maxdepth = 0;
void dfs(int v, int p) {
	// cout << "# DFS at node " << v << " with parent " << p << endl;
	par[v] = p;
	depth[v] = (p == -1 ? 1 : depth[p] + 1);
	if (depth[v] > maxdepth) maxdepth = depth[v];
	for (auto u : g[v]) {
		if (u == p) continue;
		dfs(u, v);
		subs[v] += subs[u];
	}
	subs[v]++;
}
void move(int v, int p)
{
	g[par[v]].erase(v);
	g[v].erase(par[v]);
	par[v] = p;
	g[p].insert(v);
	g[v].insert(p);
	depth[v] = depth[p] + 1;
}

void move_path(int v, int u)
{
	// cout << "# Moving path from " << v << " to " << u << endl;
	// cout << "# Depth before move: " << depth[v] << endl;
	// cout << "# Target depth: " << depth[u] << endl;
	while(v != u)
	{
		// cout << "# Moving " << v << " under " << u << endl;
		int tmp = par[v];
		move(v, u);
		v = tmp;
	}
	maxdepth = 0;
	dfs(1, -1);
}
int pick_leaf()
{
	vector <int> leaves;
	for (int i = 2; i <= N; i++) {
		if (g[i].size() == 1) {
			leaves.push_back(i);
		}
	}

	if (leaves.size() == 0) return -1;
	int idx = rng() % leaves.size();
	return leaves[idx];
}

int pick_parent(int down, int up)
{
	for (int i = 1; i <= up; i++)
	{
		down = par[down];

	}
	return (down <= 0 ? 1 : down);
}

int pick_child(int up, int down)
{
	//  cout << "pick_child: up = " << up << ", down = " << down << endl;
	if (down == 0) return up;
	if (g[up].size() == 1 && up != 1) {
		return up;
	}
	int idx = (g[up].size()==1 ? 0 : rng()%(g[up].size()-1));
	for (auto u : g[up]) {
		if (u == par[up]) continue;
		if (idx == 0) return pick_child(u, down-1);
		idx--;
	}
	return up;
}

pair <int,int> generate_query(string query_type, int qsz = -1)
{
	int u,v;
	if(query_type == "leaf")
	{
		u = pick_leaf();
		int depth_u = depth[u]-1;
		if (qsz != -1) depth_u = min(depth_u, qsz);
		else depth_u = rng() % (max(depth_u/2 - 1,2)) + 2;
		v = pick_parent(u, depth_u);
		return {v,u};
	}
	else if(query_type == "first")
	{
		u = pick_child(1, 1);
		int depth_u;
		if (qsz != -1) depth_u = qsz;
		else depth_u = rng() % (max(maxdepth/2 - 2,1)) + 2;
		v = pick_child(u, depth_u);
		return {u,v};
	}
	else if(query_type == "random")
	{
		u = pick_child(1,1 + rng() % (max(2,maxdepth - 1)));
		// cout << "u: " << u << endl;
		int depth_u = depth[u];
		if (qsz != -1) depth_u = min(qsz, depth_u);
		else depth_u = rng() % (max(depth_u/2 - 1,1)) + 2;
		// cout << "depth_u: " << depth_u << endl;
		v = pick_parent(u, depth_u);
		return {v,u};
	}
	return generate_query("random", -1);
}

void generate_tree(string tree_type) {

    std::stringstream buffer;

	if(tree_type == "random_prim") 
		buffer << Tree::randomPrim(N,2).shuffled();
	else if(tree_type == "random_kruskal") 
		buffer << Tree::randomKruskal(N).shuffled();
	else if(tree_type == "bamboo") 
		buffer << Tree::bamboo(N).shuffleAllBut({0});
	else if(tree_type == "binary") 
		buffer << Tree::binary(N).shuffleAllBut({0});
	else if(tree_type == "star") 
		buffer << Tree::star(N).shuffleAllBut({0});
	else if(tree_type == "caterpillar") 
		buffer << Tree::caterpillar(N,60000).shuffled();
	else if(tree_type == "random_prim_2") 
		buffer << Tree::randomPrim(N,2);
	else
		buffer << Tree::randomKruskal(N).shuffled();

	int u,v;
    for (int i = 1; i < N; i++){
        buffer >> u >> v;
        u++; v++;
        edges.push_back({u,v});
        g[u].insert(v);
        g[v].insert(u);
    }
}


int main(int argc, char* argv[]) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	N = stoi(argv[1]);
	Q = stoi(argv[2]);

	string tree_type = argv[3];


	vector<pair <string,int> > types;
	if(argc >= 5) {
		for (int i = 4; i < argc; i++) {
			string s = argv[i];
			size_t pos = s.find(':');
			if (pos != string::npos) {
				string t = s.substr(0, pos);
				int val = stoi(s.substr(pos+1));
				types.push_back({t, val});
			} else {
				types.push_back({s, -1});
			}
		}	
	}

	generate_tree(tree_type);
	dfs(1, -1);
	cout << N << " " << Q << "\n";
	for (auto [u,v] : edges) {
		cout << u << " " << v << "\n";
	}

	for (int i = 0; i < Q; i++) {
		string qt;
		int qsz = -1;
		int idx = rng() % types.size();
		qt = types[idx].first;
		qsz = types[idx].second;
		// cout << "# Query type: " << qt;
		// cout << ", size limit: " << qsz << endl;
		auto [u,v] = generate_query(qt, qsz);
		cout << u << " " << v << endl;
		move_path(v, u);
		// maxdepth = 0;
		// dfs(1, -1);

	}
	// cout << "OK" << endl;
}