SP18522 FBTOURS - Tours

Facebook 总部是一个神秘而引人注目的地方，充满了神奇的代码和商业机密。如果外人能够突破由一整队保安及更强大的保安狐狸保护的围墙，整个公司可能会陷入瘫痪！ 但实际上，这里经常会举办参观活动…… 园区由 $N$（$1 \leq N \leq 10^5$）栋建筑组成，之间有 $M$（$1 \leq M \leq 10^6$）条步行道相互连接。第 $i$ 条步行道连接建筑 $A_i$ 和 $B_i$（$1 \leq A_i, B_i \leq N$，$A_i \neq B_i$），并且任意两栋建筑之间至多只有一条步行道直接相连。除此之外，没有其他途径可以在建筑间移动。 在 $D$（$1 \leq D \leq 10^6$）天的时间内，总部每天都会发生一些事情。第 $i$ 天的事件类型用字符 $E_i$ 表示。如果 $E_i = "T"$，就意味着这天会有参观活动；否则，$E_i = "S"$，则表示会进行安全检查。 如果第 $i$ 天举行参观活动，游客将从建筑 $X_i$ 进入，最终从建筑 $Y_i$ 离开（$1 \leq X_i, Y_i \leq N$，$X_i \neq Y_i$）。如果这两个建筑之间没有通过步行道相连，参观将被取消，游客们只能获得一件 Facebook T 恤并被请出园区。如果参观顺利进行，大批游客将从建筑 $X_i$ 通过多种路线到达建筑 $Y_i$。每条路线不允许重复经过同一条步行道（即使是反方向也不行），但路线可能会多次经过同一建筑，包括起点 $X_i$ 和终点 $Y_i$。期间，部分游客可能会“迷路”并离开队伍。虽然当天的安全级别会影响他们被发现的数量，但所有可能的有效路线涉及的每座建筑中，总会有 $O_i$（$1 \leq O_i \leq 1000$）名游客被留在其中。幸好他们大多带了相机，可以自娱自乐等待救援。 另一方面，如果第 $i$ 天进行了安全检查，保安（和狐狸）会仔细搜索建筑 $Z_i$（$1 \leq Z_i \leq N$）是否留有之前参观活动遗留下的闯入者，并礼貌地将他们护送出总部（当然，也会发给他们一件 Facebook T 恤）。 由于公司对一切数据的记录充满兴趣，你被雇来统计每次检查时发现的外来者人数。不过，为了更具挑战性，你需要编写程序，依据园区地图和事件安排来预测这些数值！

第一行：1 个整数 $T$（$1 \leq T \leq 20$），表示测试用例的数量。 **对于每个测试用例：** 第一行：3 个整数 $N$、$M$ 和 $D$。 接下来 $M$ 行：每行 2 个整数 $A_i$ 和 $B_i$，表示第 $i$ 条步行道连接的建筑。 接下来 $D$ 行：每行为 1 个字符 $E_i$，如果 $E_i = "T"$，则后面为 3 个整数 $X_i$、$Y_i$ 和 $O_i$；如果 $E_i = "S"$，则后接 1 个整数 $Z_i$，表示第 $i$ 天的事件。

**对于每个测试用例：** 输出 1 个整数，表示被护送出园区的人数总数，对 $10^9+7$ 取模后的结果。 **本翻译由 AI 自动生成**