量子怪物是一种奇特的生物，它以波函数的形式同时存在于不同的世界线中。只要还存在一条量子怪物尚未被发现的世界线，你就永远无法捕获它。

现在，有一个量子怪物隐藏在一个包含 $n$ 个节点和 $m$ 条边的连通无向图中。你希望捕获它。整个过程按以下循环进行：

1. 量子怪物沿着图中的一条边移动到相邻节点。
2. 你选择图中的一些节点进行一次观测。你可以获知量子怪物是否在你观测的节点集合中。
3. 如果你掌握的历史信息足以唯一确定量子怪物的位置，则捕获成功，循环结束。否则，返回第 1 步。

你想知道是否有可能捕获这个量子怪物。换句话说，确定是否存在一种捕获策略，使得无论量子怪物的初始位置和移动计划如何，你都能在有限步数内唯一确定其位置。

输入格式

第一行包含一个整数 $T$ ($1 \le T$)，表示测试用例的数量。

对于每个测试用例，第一行包含两个整数 $n$ 和 $m$ ($2 \le n, 1 \le m \le 10^6$)，分别表示图中的节点数和边数。

接下来的 $m$ 行，每行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le n$)，表示图中存在一条连接 $u$ 和 $v$ 的无向边。

保证所有图均为连通无向图，且没有自环或重边，所有测试用例的 $m$ 之和不超过 $10^6$。

输出格式

对于每个测试用例，如果存在捕获策略，则输出一行字符串 YES，否则输出 NO。

样例

输入 1

3
3 3
1 2
2 3
3 1
4 4
1 2
2 3
3 4
4 1
6 6
1 2
2 3
3 4
4 5
5 6
6 1

输出 1

NO
YES
NO