在 ICPCCamp 中，有 $n$ 个城市和 $m$ 条（双向）道路连接这些城市。第 $i$ 条道路连接第 $a_i$ 个城市和第 $b_i$ 个城市。可能存在连接城市自身的道路，也可能存在连接同一对城市的多条道路。

Bobo 有 $q$ 个旅行计划。第 $i$ 个计划是从第 $u_i$ 个城市前往第 $v_i$ 个城市。他想知道每个计划所需经过的最少道路数量。保证所有城市都是连通的。

输入格式

第一行包含 3 个整数 $n, m, q$ ($1 \le n \le 10^5, 0 < m - n < 100, 1 \le q \le 10^5$)。

接下来的 $m$ 行，第 $i$ 行包含 2 个整数 $a_i, b_i$ ($1 \le a_i, b_i \le n$)。

最后的 $q$ 行，第 $i$ 行包含 2 个整数 $u_i, v_i$ ($1 \le u_i, v_i \le n$)。

输出格式

输出 $q$ 行，每行一个整数 $l_i$，表示从城市 $u_i$ 到城市 $v_i$ 所需经过的最少道路数量。

样例

样例输入 1

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

样例输出 1

0
1
2

样例输入 2

1 2 1
1 1
1 1
1 1

样例输出 2

0