OUPC2025 OPENコンテスト 2026/03/29 09:00 ~ 2026/03/29 14:00 5:00:00.000

A Distance Query

問題
制限時間: 2 sec メモリ制限: 1024 MB
Distance Query
Statement

\(2N\) 頂点の無向完全グラフがあります。頂点 \(u\) と頂点 \(v\) を結ぶ辺の重みは \((u+v) \bmod 2\) です。

このグラフに対して、下記の操作を行います。

  • 各 \(i=1,2,\dots, M\) に対して、頂点 \(u_i\) と頂点 \(v_i\) を結ぶ辺を削除する。

下記で表される \(Q\) 個のクエリを処理してください。

  • \(i\) 番目のクエリ \((s_i, t_i)\) : 頂点 \(s_i\) から頂点 \(t_i\) へのパスが存在するかどうかを判定し、存在するならば頂点 \(s_i\) から頂点 \(t_i\) へのパスに含まれる重みの総和としてあり得る最小値を求めよ。

Input

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

\(N~M~Q\)
\(u_1~v_1\)
\(u_2~v_2\)
\(\vdots\)
\(u_M~v_M\)
\(s_1~t_1\)
\(s_2~t_2\)
\(\vdots\)
\(s_Q~t_Q\)

入力は以下の制約をすべて満たします。

  • \(1\leq N\leq 10^5\)
  • \(1\leq M \leq 2\times 10^5\)
  • \(1\leq Q\leq 2\times 10^5\)
  • \(1\leq u_i \lt v_i\leq 2N~(1\leq i\leq M)\)
  • \((u_i,v_i)\neq(u_j,v_j)~(1\leq i \lt j\leq M)\)
  • \(1\leq s_i \lt t_i \leq 2N~(1 \le i \le Q)\)
  • 入力はすべて整数

Output

\(Q\) 個のクエリを処理してください。

\(i~(1\leq i\leq Q)\) 行目には、\(i\) 番目のクエリについて頂点 \(s_i\) から頂点 \(t_i\) へのパスが存在するならば重みの総和の最小値を、存在しないならば -1 を出力してください。

Scoring

以下の追加制約を満たすデータセットに正解した場合、部分点が与えられます。

  • (10点): \(M = 1, Q = 1\)
  • (25点): \(Q = 1\)
  • (65点): 追加制約はありません。

Examples

Input 1
2 4 6
1 3
2 4
1 2
2 3
1 2
1 3
1 4
2 3
2 4
3 4
Output 1
-1
2
1
-1
-1
1
Input 2
5 30 5
2 6
2 5
1 5
5 7
4 6
5 9
4 9
3 9
6 8
3 7
8 9
1 3
5 6
1 6
2 10
2 3
7 9
1 7
9 10
1 10
4 10
5 10
1 4
3 8
8 10
2 9
7 10
3 4
4 5
4 7
1 5
1 10
2 3
4 8
3 9
Output 2
2
1
1
0
2

サンプル