题目内容

现在发的动态都有点赞功能。

如果A发的动态。B点赞了$x$次。那么B对A的赞同度为$x$，记为$f(B,A)$,并且$f(B,A)$和$f(A,B)$不一定相等。

并且赞同度具有传递性。$f(A,B)=max(f(A,B),min(f(A,C),f(C,B)))$,可以多次传递。

现在有几个人，他们之间有$m$条点赞记录。

现在有$Q$次询问，每次询问输入$u,v$(空格隔开)，询问$f(u,v)$的值。

输入描述

第一行输入三个整数$n,m,Q(1≤ n ≤100,1≤ m ≤ 10^5 ,1≤ Q ≤ 10^3)$

接下来$m$行，每行输入$u,v$(代表$u$给$v$点了一次赞,$1≤u,v≤n$)

接下来$Q$行，每行输入$u,v(1≤u,v≤n)$。

输出描述

对于每一个询问输出一个整数表示答案。

样例1

输入

2 7 4
1 1
1 2
1 2
2 1
2 1
2 1
2 2
1 1
1 2
2 1
2 2

输出

2
2
3
2