← 返回题目列表

Codeforces · 2120/G

G. 欧拉线图

中文机器翻译题面 查看原题

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".

您可以在任何情况下输出答案(大写或小写)。例如,字符串“是", "是的", "是“,和”是”将被视为积极响应。

示例

输入
复制

4
5 5 2
1 2
2 3
3 4
4 5
5 1
5 6 1
1 2
2 3
3 4
4 5
5 1
1 3
10 11 3
1 2
2 3
3 4
4 5
4 6
4 7
5 7
6 7
7 8
8 9
9 10
7 8 2
1 3
2 3
1 4
4 5
2 5
1 6
6 7
2 7

输出
复制

YES
NO
YES
NO

注意

对于第一个测试用例, $$$L^2(G)$$$ 与 $$$G$$$ 本身同构。因此,由于 $$$G$$$ 具有欧拉轨迹,因此 $$$L^2(G)$$$ 也具有欧拉轨迹。

对于第二个测试用例,$$$L(G)$$$如下所示(图中$$$L(G)$$$的顶点$$$i-j$$$对应于$$$G$$$的顶点$$$i$$$和$$$j$$$之间的边)。可以证明这不存在欧拉迹。