「题目描述」

给一张无向图，边有黑白两种颜色，现在你有一堆反色刷，可以从任意点开始刷，经过若干条边后回到起点。

现在要询问至少需要多少个反色刷可以使这张图所有边都变成白色。

因为某种原因，边的颜色是会改变的，于是。。

需要支持以下操作：

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

「数据范围」

30%   n <= 20, m <= 29 ,q <= 64

60%   n <= 5000, m <= 5215 ,q <= 11308

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

来自出题人cxjyxxw_me的题解

首先猜想一个性质：如果有某个点连出的黑边度为奇数，则无解，否则必然有解。

证明：用欧拉回路去模拟，易证。

再猜想一个性质：如果有解的话，ans=图中含有黑边的联通块数。

证明：首先构造一个可行解，随便找一个有黑度的点，随便走向一个连出的黑边，一直走，直到回到这个点为止(显然一定会回到这个点)。现在考虑在同一个联通块的两个可行路径，设两个路径分别为u->blabla_u->u和v->blabla_v->v，他们的起点必然联通,设这段路径为u_v,则这两个路径可以合并为u->u_v->v->blabla_v->v->u_v->u->blabla_u->u。最后一个联通块的所有路径可以合并为一个，证毕。