Дано дерево $T$ с $n$ вершинами и $m$ пар вершин.

Для каждой из $m$ пар необходимо выбрать направление, чтобы получить $m$ ориентированных путей в дереве, удовлетворяющих следующему условию:

• Для каждого ребра $(u, v)$ в дереве пусть $l$ — количество ориентированных путей, проходящих из $u$ в $v$, а $r$ — количество путей, проходящих из $v$ в $u$. Необходимо, чтобы выполнялось условие $|l - r| \leq 1$.

Можно доказать, что решение всегда существует.

Входные данные

Первая строка содержит два целых положительных числа $n$ и $m$, обозначающих количество вершин в дереве и количество пар вершин соответственно.

Следующие $n-1$ строк содержат по два целых положительных числа $u, v$, описывающих ребро дерева.

Следующие $m$ строк содержат по два целых положительных числа $a, b$ ($a \neq b$), описывающих пару вершин.

Выходные данные

Выведите $m$ строк. В $i$-й строке выведите либо $a, b$, либо $b, a$, что будет означать выбранное направление для $i$-й пары вершин.

Примеры

Пример 1

Входные данные

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

Выходные данные

3 2
2 4

Подзадачи

Для $20\%$ данных гарантируется, что $m \leq 8$.

Для $40\%$ данных гарантируется, что $m \leq 16$.

Для еще $20\%$ данных гарантируется, что дерево является цепью (существует ребро между $i$ и $i+1$).

Для еще $20\%$ данных гарантируется, что дерево является «звездой» (существует ребро между $1$ и $i$).

Для $100\%$ данных гарантируется, что $1 \leq n, m \leq 10^5$.