You are given a tree $T$ with $n$ vertices and $m$ pairs of vertices.

For each of the $m$ pairs, you must assign a direction to form $m$ directed paths on the tree such that:

• For every edge $(u, v)$ in the tree, let $l$ be the number of directed paths that traverse from $u$ to $v$, and $r$ be the number of directed paths that traverse from $v$ to $u$. The condition $|l - r| \leq 1$ must be satisfied.

It can be proven that a solution always exists.

Input

The first line contains two positive integers $n$ and $m$, representing the number of vertices in the tree and the number of vertex pairs, respectively.

The next $n-1$ lines each contain two positive integers $u$ and $v$, representing an edge in the tree.

The next $m$ lines each contain two positive integers $a$ and $b$ ($a \neq b$), representing a vertex pair.

Output

Output $m$ lines. For the $i$-th line, output either the pair $a, b$ or $b, a$ as provided in the input, representing the direction of the path.

Examples

Examples 1

Input

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

Output

3 2
2 4

Subtasks

For $20\%$ of the data, $m \leq 8$.

For $40\%$ of the data, $m \leq 16$.

For another $20\%$ of the data, the tree is a chain (edges exist between $i$ and $i+1$).

For another $20\%$ of the data, the tree is a star graph (edges exist between $1$ and $i$).

For $100\%$ of the data, $1 \leq n, m \leq 10^5$.