[AdditionalFile5591.zip](file://AdditionalFile5591.zip?type=additional_file)

#5591. 「PA 2017 Final」Przesył

标签: 传统 | 时间限制: 9000 ms | 内存限制: 256 MiB |

题目描述

题目译自 PA 2017 Final Przesył

一年多以前，Bajtazar 成为了在字节国（Bajtocja）旅行的爱好者。这个国家有 $n$ 座城市，由 $m$ 条双向道路连接。Bajtazar 喜欢上了非凡的旅行。在这些旅行中，他从某座城市出发，沿着字节国的道路行进，访问字节国的不同城市，最终返回起始城市。在旅途中，他既不能两次访问任何城市（起始城市除外），也不能两次使用任何一条道路。

字节国的所有道路都是黑色的。Bajtazar 对此并不满意，在下一次非凡的旅行中，他会将走过的每条道路都涂成金丝雀黄。他有多少种不同的方式来给道路上色呢？如果存在一条道路在两种上色方案中颜色不同，我们就认为这两种上色方案是不同的。

输入格式

输入的第一行包含三个整数 $n, m, q$ $(2 \le n \le 3000, 1 \le m \le 500000, 1 \le q \le 500000)$。

接下来的 $m$ 行描述了道路连接；第 $i$ 行包含两个自然数 $u_i, v_i$ $(1 \le u_i, v_i \le n, u_i \neq v_i)$，表示编号为 $u_i$ 和 $v_i$ 的城市之间有一条连接。道路按照它们在输入中出现的顺序从 $1$ 到 $m$ 编号。一对城市之间可能存在多条道路。

接下来是 $q$ 个查询的描述。单个查询的描述以包含自然数 $r_i$ $(1 \le r_i \le 100)$ 的一行开始，即维修中道路的数量。随后是受影响连接的描述。它由 $r_i$ 行组成；每一行描述一个受影响的连接，并包含三个数字 $x, p_{uv}, p_{vu}$ $(0 \le x \le m, p_{uv}, p_{vu} \in \{0,1\}, p_{uv}+p_{vu} \ge 1)$。如果我们用 $S_i$ 表示从第一个到第 $(i-1)$ 个（含）查询结果的总和，那么维修将影响编号为 $j := ((x + S_i) \bmod m) + 1$ 的连接。如果 $p_{uv}=1$，那么从城市 $u_j$ 到 $v_j$ 的通行将变得不可能。如果 $p_{vu}=1$，那么从城市 $v_j$ 到 $u_j$ 的通行将变得不可能。

你可以假设，在单个查询中，$x$ 的值是互不相同的。此外，所有查询中受影响的道路总数不超过 $500000$ 条。

输出格式

对于每个查询，输出单独一行，表示能收到所有其他孩子贺卡的儿童数量。

样例

输入

4 4 3
1 2
4 3
2 3
1 3
2
3 1 1
1 0 1
3
1 1 0
0 1 0
3 1 0
1
1 1 1

输出

3
1
0

在第一个查询中，我们完全封闭了 $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$ 号道路（位于 $4$ 和 $3$ 之间）被封锁。在这种情况下，没有孩子能收到所有贺卡。