#BZOJ3706. 反色刷

反色刷

No submission language available for this problem.

题目描述

给一张无向图,边有黑白两种颜色,现在你有一堆反色刷,可以从任意点开始刷,经过若干条边后回到起点。
现在要询问至少需要多少个反色刷可以使这张图所有边都变成白色。
因为某种原因,边的颜色是会改变的,于是。。
需要支持以下操作:
1 x  把第x条边反色(编号从0~m-1)
2   询问当前图中最少需要多少个反色刷

输入格式

第一行两个整数n m表示这张图有n个点m条边
接下来m行 每行3个整数 u v c表示一条无向边和这条边的颜色(0为白色 1为黑色)
接下来一个整数q 表示有q个操作
接下来q行为操作 描述如上

输出格式

对于每个询问 输出一行一个整数
表示最少需要的反色刷个数 如果没有合法方案输出-1

6 6
1 2 1
2 3 1
1 3 1
4 5 1
5 6 1
4 6 1
14
2
1 0
2
1 1
1 2
2
1 3
1 4
1 5
2
1 3
1 4
1 5
2
2
-1
1
0
1

数据范围与约定

100%  n,m,q <= 1000000, c < 2,没有重边自环