“环银河系航行计划所面临的最大危险是失败主义。” 章北蚤非常严肃地对你说，“失败主义的思想根源，主要是盲目的技术崇拜，轻视或忽视人的精神和主观能动性在发展工质发动机中的作用。” 为了避免失败主义在军队中的蔓延，章北蚤建议先进行清扫银河计划，提振士气，增强信心。

银河系共有 $n$ 颗行星，编号为 $1,\dots ,n$。环银河系航行可能会经过的无向航道共有 $m$ 条，第 $i$ 条航道连接 $x_i$ 号行星和 $y_i$ 号行星 $(x_i\ne y_i)$，用 $(x_i,y_i)$ 表示。保证同一条航道不会被重复列举多次。

由于部分航道存在容易被撞上的小行星带，初始时一部分航道是可通行的，一部分的航道是不可通行的。章北蚤说的清扫银河计划，就是希望你先向宇宙发射跳蚤激光，远距离清除所有阻碍计划的小行星带，将所有航道变得可通行。

如果跳蚤激光照射到了一个航道上，则该航道的通行状态会被翻转：如果一个航道原本不可通行，那么被照射后航道上的小行星带会被清除，航道也会变得可通行；反之若该航道原本可通行，那么跳蚤激光会因为未击中目标而在附近的宇宙空间中胡乱狂轰乱炸，炸出小行星带，导致该航道变得不可通行。

跳蚤激光只能批量发射，不能单独发射。发射方式只有如下两种：

• 选择一个由行星组成的简单环，发射跳蚤激光后，任意一条环路上的航道都会受到跳蚤激光照射。也就是说，选出一个由不同的行星编号组成的序列 $p_1,\cdots ,p_k$（$2\le k\le n$），使得对于所有 $1\le i\le k$ 都存在航道 $(p_i,p_{(imodk)+1})$。在发射跳蚤激光后，任意一条形如 $(p_i,p_{(imodk)+1})$ 的航道的通行状态都会被翻转；特别的，如果简单环长度为2，则这一条边会被翻转两次。
• 把每个行星标记为黑色或者白色，发射跳蚤激光后，任意一条两端行星颜色不同的航道都会受到跳蚤激光照射。也就是说，对于所有的航道 $(x_i,y_i)$，如果 $x_i$ 和 $y_i$ 号行星的颜色不同，那么 $(x_i,y_i)$ 航道的通行状态会被翻转。

发射跳蚤激光的费用非常昂贵，所以章北蚤要求你判断是否能使用不超过 $m+1$ 次发射就能完成清扫银河计划。

输入格式

本题有多组数据。

第一行一个整数 $T$ 表示数据组数。

接下来 $T$ 组数据，对于每组数据：

第一行两个正整数 $n,m$。含义同题面。

接下来 $m$ 行，一行三个整数 $x_i,y_i,c_i$（$1\le x_i,y_i\le n,x_i\ne y_i,c_i\in \{0,1\}$）表示一条航路。若 $c_i$ 为 $0$，则该航道在初始时可通行，否则该航路在初始时不可通行。

输出格式

对于每组数据，一行一个字符串表示答案。

若对于一组数据可以完成目标，则输出yes,否则输出no。

注意输出字符串必须仅包含小写字母，也就是说输出Yes,nO会被判断为错误答案。

样例一

input

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

output

yes
no

explanation

第一个测试点可以依次进行如下操作：

• 将 $\{1,3\}$ 染黑其余染白，进行第二种操作，航道$(1,2),(2,3)$状态翻转。此时所有航道均不开放。
• 选择简单环$1-2-3-1$，进行第一种操作，航道$(1,2),(1,3),(2,3)$翻转。此时所有航道均开放。

同时发射跳蚤激光的次数为$2$，没有超过$4$次的限制，因此存在解。

第二个测试点不存在一个在$5$步内将所有航道开放的方案。

样例二

见样例数据下载

限制与约定

子任务1 ($20$分)：$n\le 10,m\le 15$。

子任务2 ($20$分)：$n\le 30,m\le 100$。

子任务3 ($30$分)：$n\le 100,m\le 500$。

子任务4 ($30$分)：无特殊限制。

对于所有测试数据，满足 $1\le T\le 10,1\le n\le 300,0\le m\le \frac{n(n-1)}{2}$。

保证将航道抽象成边，行星抽象成点后形成的无向图中不存在自环，不存在重边。

时间限制：$1\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$

下载

样例数据下载