红蓝图
题号：NC212402
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

有一张 n 个点，m 条边的无向图。点从 0 到 n-1 编号。边有边权和颜色，颜色为红色和蓝色中的一种。给定 q 组询问，每次给定两个参数 x,t。删除边权大于 t 的红色边和边权小于 t 的蓝色边。如果此时两个点 x,y 既有仅经过红色边的路径相连，又有仅经过蓝色边的路径相连，那么称这两个点连通。求与编号为 x 的点连通的点的数量（包括 x 本身）。询问间相互独立，每次询问的删除不会影响其他询问。

输入描述:

输入共 m+q+1 行。

第一行三个整数 n,m,q，表示图的点数、边数和询问数。

接下来 m 行，每行三个整数 x,y,c，表示点 x 和点 y 之间存在一条边，若这是输入的第 i 条边（从 1 开始数到 m），该边的边权是 i。若 c=0 则这条边为红色边，c=1 则这条边为蓝色边。可能存在自环和重边。

接下来 q 行，每行两个整数，表示一组询问的 x,t。

输出描述:

输出共 q 行，第 i 行表示第 i 组询问的答案。
示例1

输入

复制 
3 4 5
1 0 0
2 1 0
0 1 1
2 1 1
1 1
1 2
1 4
2 5
2 3

输出

复制 
2
3
2
1
3

备注:



 


本题的输入输出量可能很大，您需要使用快速的输入输出方式。您可以使用如下的模板：

https://paste.ubuntu.com/p/NYKBd45xwZ/