问题描述

给定一棵 $n$ 个结点的树（结点标号 $1 \dots n$ ）以及树中结点的边，结点 $s$ 为树的根。 有 $m$ 次询问，请求出每次询问的两个结点 $x$ 和 $y$ 的最近的公共祖先结点。

输入格式

第 $1$ 行输入 $3$ 个整数 $n$、$m$、$s$（$n≤500000$，$m≤500000$，$1≤s≤n$）； 接下来 $n-1$ 行，每行两个整数 $a$ 和 $b$ ，结点 $a$ 和 $b$ 是父子关系，但不保证 $a$ 是$b$ 的父，数据保证一定能构成树； 接下来 $m$ 行，每行两个整数 $x$，$y$，表示要求出 $x$ 和 $y$ 结点的公共祖先。

输出格式

输出 $m$ 行，每行一个整数，表示 $m$ 次询问求出的结果。

样例

输入

5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5

输出

4
4
1
4
4