$n$ 個の頂点を持つ木 $T$ と、$m$ 個の頂点対が与えられます。

これら $m$ 個の各頂点対に対して向きを一つ定め、木上の $m$ 本の有向パスを得ることを考えます。以下の条件を満たすようにしてください。

• 木の各辺 $(u, v)$ について、$m$ 本の有向パスのうち $u$ から $v$ へ向かうパスの数を $l$、$v$ から $u$ へ向かうパスの数を $r$ としたとき、$|l - r| \leq 1$ を満たすこと。

解が必ず存在することが証明されています。

入力

1 行目に、木の頂点数と頂点対の数を示す 2 つの正整数 $n, m$ が与えられます。

続く $n-1$ 行には、木の辺を表す 2 つの正整数 $u, v$ が与えられます。

続く $m$ 行には、各頂点対を表す 2 つの正整数 $a, b$ ($a \neq b$) が与えられます。

出力

$m$ 行出力してください。$i$ 行目には、入力された $i$ 番目の頂点対に対して、パスの向きに応じて $a, b$ または $b, a$ を出力してください。

入出力例

入力 1

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

出力 1

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$ を満たす。