Postcards

Bithuania has $n$ cities connected with $m$ bidirectional roads. Currently, there exists a path between every pair of cities. Each city has one child living in it. Every child would like to send a Christmas postcard to every other child. Unfortunately, the ongoing Christmas period means some roads are being renovated. Because of this, postcards can be sent in only one direction on some roads, and cannot be sent along others at all.

The government of Bithuania has drawn up several plans for shutting down roads. For each plan, in order, find the number of children who can receive a postcard 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 describe the road network: the $i$-th line contains two integers $u_i$, $v_i$ ($1 \le u_i, v_i \le n$, $u_i \neq v_i$), meaning a road between cities $u_i$ and $v_i$. Roads are numbered $1$ through $m$ in input order. A pair of cities may be connected by more than one road.

Then come $q$ shutdown plans, numbered $1$ through $q$. The $i$-th plan starts with a line containing an integer $r_i$ ($1 \le r_i \le 100$), the number of renovated roads. Then $r_i$ lines follow, each describing one shut down road with three numbers $x$, $p_{uv}$, $p_{vu}$ ($0 \le x < m$, $p_{uv}, p_{vu} \in \{0, 1\}$, $p_{uv} + p_{vu} \ge 1$).

Let $S_i$ be the sum of the answers to plans $1$ through $i-1$. The $i$-th plan refers to road $j = ((x + S_i) \bmod m) + 1$. If $p_{uv} = 1$, road $j$ cannot be used to travel from city $u_j$ to city $v_j$. If $p_{vu} = 1$, road $j$ cannot be used to travel from city $v_j$ to city $u_j$.

For each plan, the values of $x$ are distinct. The sum of all $r_i$ does not exceed $500\,000$. Because each plan depends on earlier answers, the plans must be processed online.

For every shutdown plan, print one line with the number of children who can receive a postcard from every other child.

In the first plan, road 4 (connecting cities 1 and 3) is closed completely and road 2 is partially closed (travel from 3 to 4 is not possible). Children in cities 1, 2, and 3 can receive postcards from all other children.

In the second plan, $S_2 = 3$. Roads 1, 4, and 3 are partially blocked: travel from 1 to 2, from 1 to 3, and from 2 to 3 is disallowed, respectively. Only the child in city 1 can receive a postcard from all other children.

In the last plan, $S_3 = 4$. Road 2 is blocked. No child can receive a postcard from all other children.