엽서

비타니아에는 $n$개의 도시가 있고, $m$개의 양방향 도로로 연결되어 있다. 현재 모든 도시 쌍 사이에 경로가 존재한다. 각 도시에는 어린이가 한 명씩 살고 있다. 모든 어린이는 다른 모든 어린이에게 크리스마스 엽서를 보내고 싶어 한다. 하지만 크리스마스 연휴 동안 일부 도로를 보수하고 있다. 이 때문에 일부 도로에서는 엽서를 한쪽 방향으로만 보낼 수 있고, 일부 도로로는 엽서를 전혀 보낼 수 없다.

비타니아 정부는 도로 통제 계획을 여러 개 세웠다. 계획을 하나씩 차례로 보면서, 다른 모든 어린이로부터 엽서를 받을 수 있는 어린이의 수를 구하라.

첫 줄에 정수 $n$, $m$, $q$가 주어진다 ($2 \le n \le 3000$, $1 \le m \le 500\,000$, $1 \le q \le 500\,000$). 이후 $m$개의 줄에 도로망이 주어진다. $i$번째 줄에는 도시 $u_i$와 $v_i$를 잇는 도로를 나타내는 정수 $u_i$, $v_i$가 주어진다 ($1 \le u_i, v_i \le n$, $u_i \neq v_i$). 도로는 입력 순서대로 $1$번부터 $m$번까지 번호가 붙는다. 두 도시 사이에 도로가 둘 이상 있을 수도 있다.

그다음 $q$개의 통제 계획이 $1$번부터 $q$번까지 번호순으로 주어진다. $i$번째 계획은 보수 중인 도로의 수 $r_i$ ($1 \le r_i \le 100$)로 시작한다. 이어서 $r_i$개의 줄에 통제되는 도로를 하나씩 나타내는 정수 $x$, $p_{uv}$, $p_{vu}$가 주어진다 ($0 \le x < m$, $p_{uv}, p_{vu} \in \{0, 1\}$, $p_{uv} + p_{vu} \ge 1$).

$S_i$를 $1$번부터 $(i-1)$번 계획까지의 답의 합이라고 하자. $i$번째 계획이 가리키는 도로는 $j = ((x + S_i) \bmod m) + 1$번 도로이다. $p_{uv} = 1$이면 $j$번 도로로 $u_j$에서 $v_j$로 이동할 수 없다. $p_{vu} = 1$이면 $j$번 도로로 $v_j$에서 $u_j$로 이동할 수 없다.

각 계획에서 $x$ 값은 서로 다르다. 모든 계획의 $r_i$ 합은 $500\,000$을 넘지 않는다. 계획이 이전 답에 따라 정해지므로, 계획은 온라인으로 처리해야 한다.

각 통제 계획마다 한 줄에 다른 모든 어린이로부터 엽서를 받을 수 있는 어린이의 수를 출력한다.

첫 번째 계획에서는 4번 도로(도시 1과 3을 연결)를 완전히 막고, 2번 도로는 한 방향만 막는다(3에서 4로 갈 수 없다). 도시 1, 2, 3의 어린이는 다른 모든 어린이로부터 엽서를 받을 수 있다.

두 번째 계획에서는 $S_2 = 3$이다. 1번, 4번, 3번 도로는 각각 1에서 2, 1에서 3, 2에서 3으로 가는 방향을 막는다. 도시 1의 어린이만 다른 모든 어린이로부터 엽서를 받을 수 있다.

마지막 계획에서는 $S_3 = 4$이다. 2번 도로가 막혀 있다. 다른 모든 어린이로부터 엽서를 받을 수 있는 어린이는 없다.