$N$ 頂点 $N$ 辺の単純連結無向グラフ $G$ が与えられます。

頂点には $1, 2, \dots, N$ の番号が、辺には $1, 2, \dots, N$ の番号が付けられており、辺 $i$ は頂点 $u_i, v_i$ を結んでいます。また、$G$ の単純パスの長さを単純パスに含まれる辺の本数と定義します。

$1$ 以上 $N$ 以下の整数 $A, B$ が与えられます。$G$ において、頂点 $A$ から頂点 $B$ への単純パスのうち、$2$ 番目に短い単純パスの長さを求めてください。ただし、そのような単純パスが存在しない場合はその旨を報告してください。
ここで、同じ長さの単純パスが複数存在する場合、それらは互いに区別されます。

より厳密には、次の問題に答えてください。

$G$ の頂点 $A$ から頂点 $B$ への単純パスの個数を $M$ とする。$M < 2$ であるとき -1 を出力せよ。
そうでなければ、それぞれの単純パスの長さを昇順に並べた長さ $M$ の数列を $L = (L_1, L_2, \dots, L_M)$ としたとき、$L_2$ を出力せよ。

$Q$ 個の整数の組 $(A_1, B_1), (A_2, B_2), \dots, (A_Q, B_Q)$ が与えられるので、$(A, B) = (A_1, B_1), (A_2, B_2), \dots, (A_Q, B_Q)$ についてそれぞれ答えを求めてください。

単純連結無向グラフとは

単純連結無向グラフとは、次の条件をすべて満たすグラフ $G$ のことを指します。

• 自己ループ(同一の頂点を結ぶ辺)や多重辺(ある $2$ 頂点を結ぶ $2$ 本以上の辺)が存在しない。
• どの $2$ 頂点間も何本かの辺を使って互いに移動することができる。
• 辺に向きが存在しない。

単純パスとは

単純パスとは、グラフ $G$ における頂点の列のうち、各頂点間に辺が存在し、同一の頂点を含まない列のことを指します。

より厳密には、次の条件をすべて満たす頂点列 $V = (v_1, \dots, v_n)$ のことを指します。

• $1 \le i \le n - 1$ について、$G$ に頂点 $v_i$ と頂点 $v_{i+1}$ を結ぶ辺が存在する。
• $i \ne j$ ならば $v_i \ne v_j$ が成り立つ。

Hard (125点)

• $3 \le N \le 10^5$
• $1 \le u_i < v_i \le N$
• $G$ は単純かつ連結
• $1 \le Q \le 10^5$
• $1 \le A_i, B_i \le N$
• $A_i \ne B_i$
• 入力はすべて整数

Normal (25点)

• Hard の制約に以下の制約を追加
• $Q = 1$

Easy (100点)

• Hard の制約に以下の制約を追加
• $1 \le i \le N - 1 \Rightarrow u_i = i, v_i = i + 1$
• $u_N = k \quad (1 \le k \le N - 2), v_N = N$
• $Q = 1$
• $A_1 = N$
• $1 \le B_1 \le N - 1$

部分点のみ解答したい場合

部分点のみを解答したい場合、問題によっては結果が TLE となるケースが大量に発生し、ジャッジに時間がかかる可能性があります。

C++の assert 関数やPythonの assert 文などを用いて、変数の値によってプログラムを強制終了させる処理を書き加えることで TLE を防ぎ、より早く結果を得ることができます。

入力は以下の形式で標準入力から与えられます。

$Q$ 行出力してください。$i$ 行目には $(A, B) = (A_i, B_i)$ のときの答えを出力してください。

ただし、そのようなパスが存在しない場合、代わりに -1 を出力してください。