#P18180. Find Yourself

Find Yourself

Find Yourself

量子怪物是一种奇特的生物,它以波函数的形式同时存在于不同世界线中。只要仍有一条可能的世界线中怪物尚未被找到,你就无法捕获它。

现在,一个量子怪物藏在一张有 nn 个顶点、mm 条边的连通无向图中。你知道整张图,但不知道它的初始位置。捕获过程按以下顺序不断重复:

  1. 怪物沿图中的一条边移动到相邻顶点。
  2. 你选择图中的一个顶点集合,进行一次观察,得到怪物是否位于这个集合中的回答。回答只区分“在集合中”和“不在集合中”,不直接告诉你具体顶点。
  3. 如果根据全部历史信息,已经能够唯一确定怪物当前所在的顶点,就成功捕获,过程结束;否则回到第 1 步。

请判断是否存在一种捕获策略,使得无论怪物的初始位置和移动计划如何,你都能在有限步内唯一确定它的位置。

你可以根据此前的回答决定下一次观察哪些顶点。本题只要求判断这样的策略是否存在,不需要输出或实际执行策略。

输入格式

第一行包含一个整数 TT,表示测试用例数。

对于每个测试用例,第一行包含两个整数 n,mn,m。

接下来 mm 行,每行包含两个整数 u,vu,v,表示一条连接顶点 u,vu,v 的无向边。

输出格式

对于每个测试用例,若存在满足要求的捕获策略,输出一行 YES;否则输出一行 NO。

数据范围

  • 1≤T1\le T;
  • 2≤n2\le n,1≤m≤1061\le m\le10^6;
  • 1≤u,v≤n1\le u,v\le n;
  • 每张图均连通,没有自环和重边;
  • 整个输入文件中,所有测试用例的 mm 之和不超过 10610^6。

由连通性可知 n≤m+1n\le m+1,因此合法数据中可能有 n=1000001n=1000001。

样例

输入:

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

输出:

NO
YES
NO