Remove edge - MarisaOJ: Marisa Online Judge

Given a connected, undirected graph of

$n$ vertices and

$m$ edges. There are

$q$ queries, each of the form

$(e, c)$ . After removing the

$e^{th}$ edge, how many vertices are in the same connected component with

$c$ . It is guaranteed that each edge is removed at most one time. ### Input - The first line contain 3 integers

$n, m, q$ . - The next

$m$ lines, each line contains 2 integers

$u, v$ , there is an edge between

$u, v$ . - The next

$q$ lines, each line contains 2 integers

$e, c$ , a query. ### Output - Print

$q$ lines, the

$i^{th}$ is the answer to query

$i$ . ### Constraints -

$1 \le n, m, q \le 10^5$ . -

$1 \le u, v \le n$ . -

$1 \le e \le m$ . -

$1 \le c \le n$ . ### Example Input:

$4 4 3 1 2 2 3 3 4 2 4 4 4 2 3 1 1$

Output:

$4 2 1$

Topic

DSU

Rating

1200

Solution (1)

Solution