Description

There are $n$ users on Luogu, and these users form an undirected network.

Luogu’s photo sharing rule is as follows: if user $i$ shares a photo with their friend $j$, then all friends $k$ of $j$ can see this photo. User $j$ can also see this photo.

Now, user $u_i$ wants to share a photo, but they do not want user $v_i$ to see it. Without sending it to themselves, they want to know the maximum number of friends they can send it to.

Input Format

The first line contains three positive integers $n, m, q$, representing the number of users, the number of edges, and the number of queries.

The next $m$ lines each contain two numbers $x_i, y_i$, indicating that there is an undirected edge between users $x_i$ and $y_i$.

The next $q$ lines each contain two numbers $u_i, v_i$, indicating the $i$-th query.

Output Format

For each query, output one line containing one number, the answer.

6 7 8
5 1
1 4
1 6
5 6
5 4
1 2
5 3
5 3
1 1
3 6
1 5
5 6
1 4
5 2
2 6

3
0
0
1
2
2
3
0

Hint

For $20\%$ of the testdata, $1 \le n, q \le 2 \times 10^3$, $1 \le m \le 8 \times 10^3$.

For $60\%$ of the testdata, $1 \le n, q \le 2 \times 10^4$, $1 \le m \le 5 \times 10^4$.

For $100\%$ of the testdata, $1 \le n, q \le 2 \times 10^5$, $1 \le m \le 7 \times 10^5$.

It is guaranteed that there are no multiple edges and no self-loops.

Translated by ChatGPT 5