众所周知,雅利安是一个有趣的人。他决定创建有趣的图表。对于图$$$G$$$,他定义$$$G$$$的有趣图$$$G'$$$如下:
- $$$G'$$$ 的每个顶点 $$$v'$$$ 映射到 $$$G$$$ 中的非空独立集$$$^{\text{*}}$$$ 或派系$$$^{\text{†}}$$$。
- $$$G'$$$ 的顶点两两不相交并组合而成的 $$$G$$$ 的顶点集覆盖了 $$$G$$$ 的所有顶点,即 $$$G'$$$ 的顶点映射的 $$$G$$$ 的顶点集构成了 $$$G'$$$ 的顶点集的划分$$$G$$$。
- 如果一条边连接 $$$G'$$$ 中的两个顶点 $$$v_1'$$$ 和 $$$v_2'$$$,则映射到 $$$v_1'$$$ 的集合中 $$$G$$$ 的每个顶点和映射到 $$$v_2'$$$ 的集合 $$$G$$$ 的每个顶点之间都有一条边。
- 如果一条边没有连接 $$$G'$$$ 中的两个顶点 $$$v_1'$$$ 和 $$$v_2'$$$,则映射到 $$$v_1'$$$ 的集合中 $$$G$$$ 的任何顶点与映射到 $$$v_2'$$$ 的集合中 $$$G$$$ 的任何顶点之间不存在边。
众所周知,Harshith 是一个出色的人。他决定使用有趣的图表来创建自己的精美图表。对于图 $$$G$$$,如果 $$$G' '$$$ 在 $$$G$$$ 所有可能的有趣图中具有最少的顶点数,则有趣图 $$$G' '$$$ 被称为 $$$G$$$ 的极好图。
Aryan 给 Harshith $$$k$$$ 简单的无向图$$$^{\text{‡}}$$$ $$$G_1, G_2,\ldots,G_k$$$,全部位于同一顶点集 $$$V$$$ 上。 Harshith 然后想知道是否存在 $$$k$$$ 其他图 $$$H_1, H_2,\ldots,H_k$$$,所有这些都在某个其他顶点集 $$$V'$$$ 上,这样:
- $$$G_i$$$ 是 $$$H_i$$$ 对于所有 $$$i\in \{1,2,\ldots,k\}$$$ 的绝佳图表。
- 如果 V$$$ 中的顶点 $$$v\in V$$$ 映射到 $$$G_i, H_i$$$ ($$$1\leq i\leq k$$$) 对中一组大小大于 $$$1$$$ 的独立集合,则不存在 $$$G_j, H_j$$$ ($$$1\leq j\leq k, j\neq i$$$) 对,其中$$$v$$$ 映射到规模大于$$$1$$$ 的派系。
帮助 Harshith 解决他的疑问。
$$$^{\text{*}}$$$对于图$$$G$$$,如果$$$S$$$中没有两个顶点与边相连,则顶点的子集$$$S$$$称为独立集。
$$$^{\text{†}}$$$对于图 $$$G$$$,如果 $$$S$$$ 的每个顶点都通过边连接到 $$$S$$$ 的每个其他顶点,则顶点的子集 $$$S$$$ 称为团。
$$$^{\text{‡}}$$$如果图的边是无向的并且同一对顶点之间不存在自环或多条边,则该图是简单无向图。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1\leq n\leq 300, 1\leq k\leq 10$$$)。
然后,描述了 $$$k$$$ 图表。每个图形描述的第一行包含一个整数 $$$m$$$ ($$$0\leq m\leq \frac{n\cdot(n-1)}{2}$$$)。
接下来的 $$$m$$$ 行每行包含两个空格分隔的整数 $$$u$$$ 和 $$$v$$$ ($$$1\leq u, v\leq n, u\neq v$$$),表示一条边连接顶点 $$$u$$$ 和 $$$v$$$。
保证所有测试用例的所有图的$$$m$$$总和不超过$$$2\cdot 10^5$$$,并且所有测试用例的$$$n$$$总和不超过$$$300$$$。
输出
对于每个测试用例,打印“是"如果存在满足条件的$$$k$$$图;否则,“No".
您可以在任何情况下输出答案(大写或小写)。例如,字符串“是", "是的", "是“,和”是”将被视为积极响应。
示例
输入复制
35 233 45 35 163 53 41 41 22 34 24 3033 11 41 244 24 31 22 33 2033 13 21 2
输出复制
Yes Yes No
注意
对于第一个测试用例,以下是 $$$G_1、H_1$$$ 和 $$$G_2、H_2$$$ 的图表,其中 $$$G_1$$$ 是 $$$H_1$$$ 的极好图,$$$G_2$$$ 是 $$$H_2$$$ 的极好图。
在每个图中,$$$G_i$$$ 的顶点 $$$2$$$ 对应于独立集 $$$\{2\_1, 2\_2\}$$$ 对应的 $$$H_i$$$ 以及 $$$G_i$$$ 的其余顶点 $$$v\in\{1,3,4,5\}$$$ 对应于独立集/派$$$\{v\}$$$对应$$$H_i$$$(单个顶点集既可以认为是独立集,也可以认为是团)。
在第三个测试用例中,可以证明答案是“No".