013 - 通勤路
時間制限 1 秒 / メモリ制限 64 MB / 得点 12 / x 0 /
問題
PCK君が住むアイヅ町には、N個の地点と各地点をつなぐ
$N$
−
1
本の道があります。地点にはそれぞれ
1
から
$N$
までの番号がついていて、どの道も双方向に移動することができます。また、どの地点からでも、いくつかの道を通っていけば他の地点に到達できます。
株式会社IZUAのCEOであるPCK君は、日々の生活に変化を加えるため、ルーチンワークとして毎日通勤路を変えることにしています。
PCK君は、以下の条件を満たす経路で通勤します。
- 自宅の最寄りの地点 $u$ を出発し、会社の最寄りの地点 $v$ へ到着する経路である。
- $u$ と $v$ は出発時と到着時にそれぞれちょうど1度通る。
- 経路上の $u$ と $v$ 以外の各地点は高々2回まで通る。
- 経路上の各道は高々2回まで通る。
入力
入力は以下の形式で与えられる。
$N$ $s_1$ $t_1$ $s_2$ $t_2$ : $s$$N$−1 $t$$N$−1 $Q$ $u_1$ $v_1$ $u_2$ $v_2$ : $u_Q$ $v_Q$
1行目に地点の数 $N$ ( 2 ≤ $N$ ≤ 100,000 )が与えられる。続く $N$ − 1 行に、2つの地点を直接つなぐ道の情報が与えられる。 $s_i$ と $t_i$ ( 1 ≤ $s_i$ < $t_i$ ≤ $N$ )は $i$ 番目の道がつなぐ2つの地点の番号である。ただし、どの2つの地点についても、それらを直接つなぐ道は1本以下とする。続く行に質問の数 $Q$ ( 1 ≤ $Q$ ≤ 100,000 )が与えられる。続く $Q$ 行に各質問を表す2つの整数 $u_i$ と $v_i$ ( 1 ≤ $u_i$ < $v_i$ ≤ $N$ )が与えられる。
出力
出力の最後に改行を入れること。
入出力例
入力例
4 1 2 2 3 2 4 2 1 2 1 3
出力例
1 2