Chiaki 拥有一个包含 $n$ 个顶点和 $m$ 条边的图。经过简短的研究，她意识到该图可能代表一种特殊的图——$k$ 阶 Chiaki 链。

普通链是一个由连续（至少两个）顶点组成的图。每两个相邻顶点之间由一条边连接。$k$ 阶 Chiaki 链看起来与普通链略有不同。它有 $k$ 条从主链上 $k$ 个不同顶点延伸出来的子链。在每条子链的另一端，分别有一个长度为 $3, 4, \dots, k + 2$ 的简单环。$k$ 阶 Chiaki 链中不存在多余的顶点或边。

Chiaki 想知道该图是否为 $k$ 阶 Chiaki 链。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含三个整数 $n, m$ 和 $k$ ($1 \le n, m, k \le 2 \times 10^5$)，分别表示图中的顶点数、边数以及 Chiaki 链的阶数。

接下来 $m$ 行，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$ ($1 \le x_i, y_i \le n$)，表示第 $i$ 条边连接的两个顶点。

保证所有测试数据中 $m$ 的总和不超过 $2 \times 10^5$。

输出格式

对于每组测试数据，如果该图是 $k$ 阶 Chiaki 链，则输出 “Yes”，否则输出 “No”。

样例

样例输入 1

2
20 22 3
1 2
2 3
3 4
4 5
5 6
2 7
7 8
8 9
9 10
10 11
11 12
12 8
3 13
13 14
14 15
15 16
16 13
5 17
17 18
18 19
19 20
20 18
5 6 3
1 2
2 3
3 4
4 5
5 1
1 3

样例输出 1

Yes
No

说明

下图对应第一个样例。