qwq

#include <iostream>

typedef int EdgeType;
typedef int DataType;

const int MAXN{500000 + 10};
const int MAXLog{19 + 5};
int Log2[MAXN]{}, father[MAXN][MAXLog]{}, deep[MAXN]{}; //father 存储 i 点的 2 ^ k 级祖先
bool visit[MAXN];

struct Edge
{
	EdgeType end; //终点
	EdgeType next; //以 i 为起点，第一条边的存储位置，倒序
};
EdgeType head[MAXN]{};
EdgeType count{1};
Edge storage[MAXN];

void addedge(EdgeType start, EdgeType end);
void dfs(EdgeType now, EdgeType father = 0); //求出每个点的深度
int lca(int a, int b);

int main()
{
	using namespace std;
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(false);
	//memset(head, -1, sizeof(head));

	int n{}, m{}, s{};
	cin >> n >> m >> s;
	for (int i = 2; i <= n; i++)
	{
		Log2[i] = Log2[i / 2] + 1;
	}

	for (int i{}, x{}, y{}; i < n - 1; i++)
	{
		cin >> x >> y;
		addedge(x, y);
		addedge(y, x); //无向图！
	}
	dfs(s);
	for (int i{}, a{}, b{}; i < m; i++)
	{
		cin >> a >> b;
		cout << lca(a, b) << "\n";
	}
}

void addedge(EdgeType start, EdgeType end)
{
	storage[count].end = end;
	storage[count].next = head[start];
	head[start] = count++;
};

void dfs(EdgeType now, EdgeType father)
{
	if (visit[now]) return;
	visit[now] = true;
	deep[now] = deep[father] + 1; //子 = 父 + 1
	::father[now][0] = father;

	for (int i = 1; i <= Log2[deep[now]]; i++) //范围小于深度的 log2
	{
		using ::father;
		father[now][i] = father[father[now][i - 1]][i - 1]; //跳一半再跳一半
	}

	for (int edge = head[now]; edge; edge = storage[edge].next)
	{
		if(storage[edge].end != father)
			dfs(storage[edge].end, now);
	}
};

int lca(int a, int b) 
{
	if (deep[a] > deep[b]) //设 a 的深度 <= b
	{
		std::swap(a, b);
	}
	while (deep[a] != deep[b]) //直到深度相等为止
	{
		b = father[b][Log2[deep[b] - deep[a]]]; //b 向上跳
	}
	if (a == b)
	{
		return a;
	}
	for (int i = Log2[deep[a]]; i >= 0; i--) //从可能跳的最大步数开始
	{
		if (father[a][i] != father[b][i])
		{
			a = father[a][i], b = father[b][i]; //在 a, b 不相遇的情况下跳得尽量高
		}
	}
	return father[a][0];
};