18995번 - Postcards 다국어

문제

Bithuania has $n$ cities connected with $m$ bidirectional roads. Currently, there exists a path between every pair of cities. In each of these cities there lives a single child. Every child would like to send a Christmas postcard to every other child. Unfortunately, the ongoing Christmas period results in some roads being renovated. Due to difficulties, for some roads, postcards can only be transported in one direction or cannnot be transported along that road at all.

The government of Bithuania gathered a number of plans of road shutdowns. Your task is to find for each of them, one by one, the number of children that are able to get postcards from every other child.

입력

The first line contains three integers $n, m, q$ (2ドル \le n \le 3000,ドル 1ドル \le m \le 500,000円,ドル 1ドル \le q \le 500,000円$). The next $m$ lines contain the description of the road network: the $i$-th of them contains two integers $u_i, v_i$ (1ドル \le u_i, v_i \le n,ドル $u_i \neq v_i$) denoting a road between cities $u_i$ and $v_i$. The roads are numbered 1ドル$ through $m$ with respect to the order of appearance in the input. It is possible that a pair of cities is connected by more than one road.

Then, $q$ descriptions of road shutdown plans (numbered 1ドル$ through $q$) follow. The $i$-th description starts with a line containing an integer $r_i$ (1ドル \le r_i \le 100$) -- the number of renovated roads. Next, the description of roads shut down in the $i$-th plan follows.¹ It consists of $r_i$ lines; each line describes one road that is shut down and contains three numbers $x, p_{uv}, p_{vu}$ (0ドル \le x < m,ドル $p_{uv}, p_{vu} \in \{0, 1\},ドル $p_{uv} + p_{vu} \geq 1$). Let us denote by $S_i$ the sum of answers to the queries about plans 1ドル$ through ${(i-1)}$. Then, the $i$-th renovation plan includes the connection $j := ((x + S_i),円\mathrm{mod},円m) + 1$. If $p_{uv} = 1,ドル it will be impossible to travel from the city $u_j$ to the city $v_j$ using road $j$. If $p_{vu} = 1,ドル it will be impossible to travel from the city $v_j$ to the city $u_j$ using road $j$.

You can assume that for each plan, the values of $x$ are distinct. Moreover, the sum of values $r_i,ドル over all plans, does not exceed 500ドル,000円$.

1The format of this description is somewhat weird, because we would like to enforce processing the queries online.

출력

For every road shutdown plan, output one line containing the number of children that can receive a postcard from every other child.

제한

힌트

In the first plan we close completely the road 4ドル$ (connecting cities 1ドル$ and 3ドル$) and partially the road 2ドル$ (it is not possible to go from 3ドル$ to 4ドル$). The children from cities 1ドル,ドル 2ドル$ and 3ドル$ can receive postcards from all other children.

In the second query we have $S_2 = 3$. Roads 1ドル,ドル 4ドル$ and 3ドル$ are partially blocked (we disallow going from 1ドル$ to 2ドル,ドル from 1ドル$ to 3ドル$ and from 2ドル$ to 3ドル,ドル respectively). Only the child from the city 1ドル$ can receive a postcard from all other children.

In the last query $S_3 = 4$. The road 2ドル$ is blocked. In this situation no child can receive a postcard from all other children.