#P18180. Find Yourself
Find Yourself
Find Yourself
量子怪物是一种奇特的生物,它以波函数的形式同时存在于不同世界线中。只要仍有一条可能的世界线中怪物尚未被找到,你就无法捕获它。
现在,一个量子怪物藏在一张有 个顶点、 条边的连通无向图中。你知道整张图,但不知道它的初始位置。捕获过程按以下顺序不断重复:
- 怪物沿图中的一条边移动到相邻顶点。
- 你选择图中的一个顶点集合,进行一次观察,得到怪物是否位于这个集合中的回答。回答只区分“在集合中”和“不在集合中”,不直接告诉你具体顶点。
- 如果根据全部历史信息,已经能够唯一确定怪物当前所在的顶点,就成功捕获,过程结束;否则回到第 1 步。
请判断是否存在一种捕获策略,使得无论怪物的初始位置和移动计划如何,你都能在有限步内唯一确定它的位置。
你可以根据此前的回答决定下一次观察哪些顶点。本题只要求判断这样的策略是否存在,不需要输出或实际执行策略。
输入格式
第一行包含一个整数 ,表示测试用例数。
对于每个测试用例,第一行包含两个整数 。
接下来 行,每行包含两个整数 ,表示一条连接顶点 的无向边。
输出格式
对于每个测试用例,若存在满足要求的捕获策略,输出一行 YES;否则输出一行 NO。
数据范围
- ;
- ,;
- ;
- 每张图均连通,没有自环和重边;
- 整个输入文件中,所有测试用例的 之和不超过 。
由连通性可知 ,因此合法数据中可能有 。
样例
输入:
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