Aryan 最喜欢图论。嗯,不,他更喜欢用折线图向大家展示他的研究论文。为了与您开始对话,他决定给您一个有关折线图的问题。在图论的数学学科中,简单无向图$$$G$$$的线图是另一个简单无向图$$$L(G)$$$,表示$$$G$$$中每两条边之间的邻接关系。
准确地说,对于没有自环或重边的无向图 $$$G$$$,其折线图 $$$L(G)$$$ 是这样的图:
- $$$L(G)$$$ 的每个顶点代表 $$$G$$$ 的一条边。
- $$$L(G)$$$ 的两个顶点相邻当且仅当它们对应的边在 $$$G$$$ 中共享公共端点。
另外,$$$L^0(G)=G$$$ 和 $$$L^k(G)=L(L^{k-1}(G))$$$ 对于 $$$k\geq 1$$$。
欧拉轨迹是一系列边,它恰好访问图的每条边一次。该轨迹可以是路径(在不同顶点开始和结束)或循环(在同一顶点开始和结束)。在追踪过程中可以重新访问顶点,但每条边必须仅使用一次。
Aryan 为您提供了一个简单的连通图 $$$G$$$,具有 $$$n$$$ 顶点和 $$$m$$$ 边以及整数 $$$k$$$,并且保证 $$$G$$$ 具有欧拉轨迹,并且它不是路径图$$$^{\text{*}}$$$。他要求你确定 $$$L^k(G)$$$ 是否有欧拉迹。
$$$^{\text{*}}$$$路径图是一棵树,其中每个顶点都连接到至多两个其他顶点。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含三个空格分隔的整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$5 \le n \le 2 \cdot 10^5$$$, $$$n-1 \le m \le \min(\frac{n\cdot(n-1)}{2} ,2 \cdot 10^5)$$$, $$$1 \le k \le 2 \cdot 10^5$$$)。
每个测试用例接下来的 $$$m$$$ 行包含两个空格分隔的整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u,v \le n$$$, $$$u \neq v$$$),表示一条边连接顶点 $$$u$$$ 和 $$$v$$$。
保证所有测试用例的 $$$n$$$ 和 $$$m$$$ 之和不超过 $$$2\cdot 10^5$$$。
输出
对于每个测试用例,打印“是"如果 $$$L^k(G)$$$ 有欧拉迹;否则,"NO".
您可以在任何情况下输出答案(大写或小写)。例如,字符串“是", "是的", "是“,和”是”将被视为积极响应。
示例
输入复制
45 5 21 22 33 44 55 15 6 11 22 33 44 55 11 310 11 31 22 33 44 54 64 75 76 77 88 99 107 8 21 32 31 44 52 51 66 72 7
输出复制
YES NO YES NO
注意
对于第一个测试用例, $$$L^2(G)$$$ 与 $$$G$$$ 本身同构。因此,由于 $$$G$$$ 具有欧拉轨迹,因此 $$$L^2(G)$$$ 也具有欧拉轨迹。
对于第二个测试用例,$$$L(G)$$$如下所示(图中$$$L(G)$$$的顶点$$$i-j$$$对应于$$$G$$$的顶点$$$i$$$和$$$j$$$之间的边)。可以证明这不存在欧拉迹。