终抵群星 (star)

请重定向从 star.in 输入，并重定向到 star.out 输出。

题目描述

小 Z 初始时有一个 $n$ 个点，没有任何边。每一个点有一个颜色，颜色是 $0$ 或 $1$，小 Z 忘记了每个点的具体颜色，但是他记得一些别的信息。

小 Z 认为一个点对是好的，当且仅当两个点颜色相同，且这两个点在图上联通。

依次发生 $m$ 个事件，第 $i$ 个事件，连接一条边，边的两个端点为 $u_i,v_i$，小 Z 告诉你连接该边之后好的点对的数量 $S \mod 2$ 的值。

请你输出在满足小 Z 所给的所有信息的前提下，所有点中颜色为 $1$ 的个数可能的最大值。

输入格式

本题每个测试点有多组测试数据，第一行一个整数 $T$，表示测试数据组数。

对于每一组测试数据，第一行两个整数 $n,m$。

接下来 $m$ 行，每行三个整数 $u_i,v_i,s_i$，表示第 $i$ 条边的两个端点，以及有了 $1 ~ i$ 这些边后好的点对数量 $S \mod 2$ 的值。

输出格式

输出 $T$ 行，每行一个整数表示对于当前测试数据的答案，如果没有满足要求的方案，说明小 Z 给出的信息有误，输出 $-1$。

输入输出样例1

样例输入

3
5 1
4 1 0
1 2
1 1 0
1 1 0
3 4
3 3 0
2 1 1
1 2 0
3 1 0

样例输出

4
1
-1

输入输出样例2

样例输入

2
7 2
2 4 0
3 2 1
7 4
7 4 0
6 2 0
1 1 0
5 4 1

样例输出

6
5

输入输出样例3

见选手目录下的 star/star3.in 和 star/star3.ans

输入输出样例4

见选手目录下的 star/star4.in 和 star/star4.ans

数据范围

对于所有测试数据保证： $1 \leq T \leq 10,1 \leq n,m \leq 10^5,1 \leq u_i,v_i \leq n$。

令最后形成的图的连通块最大是 $C$。

• 特殊性质 A: 保证 $u_i=i,v_i=i+1,m=n-1$。

选手附加文件

star.zip