Description

给定一张无向图，每次询问两个点，求它们的公共点个数。

两个点的公共点定义为与这两个点都有直接连边的点。

Format

Input

第一行三个整数 $n, m, q$，分别表示无向图的节点数、边数以及询问的次数。

接下来 $m$ 行，每行两个整数 $x,y$，表示 $x$ 与 $y$ 之间有一条连边。保证 $x \neq y$。

接下来 $q$ 行，每行两个整数 $a,b$，询问 $a$ 与 $b$ 的公共点个数。保证 $a \neq b$。

Output

共 $q$ 行，其中第 $i$ 行表示第 $i$ 个询问的答案。

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

0
2
1

Limitation

对于前 $30\%$ 的数据，保证 $1 \le n, m, q \le 10^3$。

对于前 $60\%$ 的数据，保证 $1 \le n, m, q \le 5 \times 10^4$。

对于 $100\%$ 的数据，保证 $1 \le n, m, q \le 2\times 10^5$。

时空限制：800ms/256MB。