You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

马自立

题目描述

你现在正在夏日祭上闲逛。

夏日祭中有 $n$ 个地标点，有 $m$ 条双向道路，每条道路连接着两个地标点（不用考虑道路交叉这种事情）。

每条道路旁边都有一些摊位，其中有一些道路上的摊位你非常想去，所以你打算规划一条路径经过所有你感兴趣的道路。

但重复看到相同的景观实在是太无趣了，所以你希望不在一条道路上重复走（来回方向不同也算重复走）。

而且你讲究有始有终，你希望你出发的地点也是你结束的地点。（即路径成环）

现在你提前知道了夏日祭的规划图，打算设计一条路径（环），在每条道路最多经过一次的情况下经过所有你感兴趣的道路。

由于某些原因，你只需要判断该路径是否存在。

而且你惊奇地发现，如果只保留你感兴趣的道路和连接的地标点，得到的图竟然是连通的！

输入格式

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

对于每组数据，首先两个正整数 $n,m$，如题意所述。

接下去 $m$ 行，每行三个整数 $u,v,c$，描述一条连接地标点 $u$ 和 $v$ 的道路，若 $c=1$ 则表示你感兴趣，$c=0$ 表示你不感兴趣。

输出格式

对于每组测试数据，如果存在这样一条路径，则输出 "Yes"（不含括号）。

若不存在，则输出一行 "No" 即可。

样例

Input 1

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

Output 1

No
Yes
Yes

提示说明

对于前 $0\%$ 的数据，是样例。

对于前 $20\%$ 的数据，保证 $n,m\le 8,T\le 100$。

对于另外 $30\%$ 的数据，保证 $n\le 5000$，并且重要的道路构成一个菊花图。

对于另外 $20\%$ 的数据，保证整个图是个基环树。

对于 $100\%$ 的数据，保证 $n\le 10^5,m\le \min(\frac{n\times (n-1)}{2},2\times 10^5)$。

$\sum n \le 5\times 10^5,\sum m \le 5\times 10^5$