#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int MAXN = 1e5 + 5;
const int LOG = 20; // 2^20 > 1e5
vector<int> adj[MAXN];
vector<int> ch[MAXN];
int depth[MAXN];
int parent[MAXN][LOG];
int n, m, root;
// 预处理:计算每个节点的深度和2^k级祖先
void dfs(int u, int p) {
depth[u] = depth[p] + 1;
parent[u][0] = p;
for (int k = 1; k < LOG; ++k) {
parent[u][k] = parent[parent[u][k-1]][k-1];
}
for (int v : adj[u]) {
if (v != p) {
ch[u].push_back(v);
dfs(v, u);
}
}
}
// 查找u和v的最近公共祖先
int lca(int u, int v) {
if (depth[u] < depth[v]) {
swap(u, v);
}
// 将u提到与v同一深度
for (int k = LOG - 1; k >= 0; --k) {
if (depth[u] - (1 << k) >= depth[v]) {
u = parent[u][k];
}
}
if (u == v) {
return u;
}
// 同时向上跳
for (int k = LOG - 1; k >= 0; --k) {
if (parent[u][k] != parent[v][k]) {
u = parent[u][k];
v = parent[v][k];
}
}
return parent[u][0];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
root = 1;
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
// 预处理
dfs(root, 0);
// lca查询
// cout << lca(u, v);
return 0;
}