P8250 Friendship Problem


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.

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.

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

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