005 - 通勤路

問題

PCK君が住むアイヅ町には、N個の地点と各地点をつなぐ $N$ − 1 本の道があります。地点にはそれぞれ 1 から $N$ までの番号がついていて、どの道も双方向に移動することができます。また、どの地点からでも、いくつかの道を通っていけば他の地点に到達できます。

株式会社IZUAのCEOであるPCK君は、日々の生活に変化を加えるため、ルーチンワークとして毎日通勤路を変えることにしています。

PCK君は、以下の条件を満たす経路で通勤します。

• 自宅の最寄りの地点 $u$ を出発し、会社の最寄りの地点 $v$ へ到着する経路である。
• $u$ と $v$ は出発時と到着時にそれぞれちょうど1度通る。
• 経路上の $u$ と $v$ 以外の各地点は高々２回まで通る。
• 経路上の各道は高々２回まで通る。

PCK君は自宅と会社の移転を検討していて、移転後に何通りの通勤路を楽しむことができるか知りたがっています。 地点の数、地点同士を直接つなぐ道の情報、移転後の自宅の最寄りの地点 u と会社の最寄りの地点 v が与えられる。ただし、 u と v の組は質問としていくつか与えられる。各質問に対して、通勤路の数を求めるプログラムを作成せよ。

入力

入力は以下の形式で与えられる。

$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$

１行目に地点の数 $N$ ( 2 ≤ $N$ ≤ 100,000 )が与えられる。続く $N$ − 1 行に、２つの地点を直接つなぐ道の情報が与えられる。 $s_i$ と $t_i$ ( 1 ≤ $s_i$ < $t_i$ ≤ $N$ )は $i$ 番目の道がつなぐ２つの地点の番号である。ただし、どの２つの地点についても、それらを直接つなぐ道は１本以下とする。続く行に質問の数 $Q$ ( 1 ≤ $Q$ ≤ 100,000 )が与えられる。続く $Q$ 行に各質問を表す２つの整数 $u_i$ と $v_i$ ( 1 ≤ $u_i$ < $v_i$ ≤ $N$ )が与えられる。

出力

出力の最後に改行を入れること。

入出力例

入力例

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

出力例

1
2