Description

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

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

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

需要支持以下操作：

1 x  把第x条边反色（编号从0~m-1）

2   询问当前图中最少需要多少个反色刷

Input

第一行两个整数n m表示这张图有n个点m条边

接下来m行 每行3个整数 u v c表示一条无向边和这条边的颜色(0为白色 1为黑色)

接下来一个整数q 表示有q个操作

接下来q行为操作 描述如上

Output

对于每个询问 输出一行一个整数

表示最少需要的反色刷个数 如果没有合法方案输出-1

Sample Input

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

Sample Output

2

-1

1

0

1

Hint

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

 

 

题解

• 首先题目有解当且仅当每个点连接的黑边数量均为偶数
• 若有解答案就等于存在黑边的连通块数量
• 证明：对于一个连通块，假设当前选择了两条分别从u和v开始的不相交的路径
• 我们可以通过先走u为起点的路径，然后从u走到v，再走从v开始的路径
• 最后回到u来将这两条路径合并

代码

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5 const int N=1000005; 6 int n,m,cnt,now,q,f[N],d[N],col[N]; 7 struct edge{
   int x,y,c;}e[N]; 8 int find(int x) { return f[x]==x?x:f[x]=find(f[x]); } 9 int main()10 {11     scanf("%d%d",&n,&m);12     for (int i=1;i<=n;i++) f[i]=i;13     for (int i=1,x,y,z;i<=m;i++)14     {15         scanf("%d%d%d",&x,&y,&z),e[i].x=x,e[i].y=y,e[i].c=z;16         if (z) now-=d[x]+d[y],d[x]^=1,d[y]^=1,now+=d[x]+d[y];17         if (find(x)!=find(y)) f[find(x)]=find(y);18     }19     for (int i=1;i<=m;i++)20         if (e[i].c)21         {22             int x=find(e[i].x);23             if (!col[x]) cnt++;24             col[x]++;25         }26     scanf("%d",&q);27     for (int op,x;q;q--)28     {29         scanf("%d",&op);30         if (op==2) printf("%d\n",now?-1:cnt);31         else32         {33             scanf("%d",&x),x++;34             now-=d[e[x].x]+d[e[x].y],d[e[x].x]^=1;d[e[x].y]^=1,now+=d[e[x].x]+d[e[x].y];35             if (e[x].c)36             {37                 e[x].c=0,col[find(e[x].x)]--;38                 if (!col[find(e[x].x)]) cnt--;39             }40             else41             {42                 e[x].c=1;43                 if (!col[find(e[x].x)]) cnt++;44                 col[find(e[x].x)]++;45             }46         }47     }48     return 0;49 }