题目描述

有 $n$ 个人，编号为 $1$ 到 $n$，他们之间有一些好友关系。好友关系是双向的。

接下来有 $q$ 次询问，每次询问两个人 $x,y$ 有多少个共同好友。

输入格式

第一行三个整数 $n,m,q$。

接下来 $m$ 行，每行两个整数 $u,v$，表示 $u$ 和 $v$ 是好友。

接下来 $q$ 行，每行两个整数 $x,y$，表示一次询问。

输出格式

对于每次询问，输出一行一个整数，表示共同好友数量。

样例

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

1
1
1

数据范围与提示

• 对于 $100\%$ 的数据，$1 \le n \le 2000$，$0 \le m \le 200000$，$1 \le q \le 200000$。