시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 256 MB2000.000%

문제

Chiaki has a graph consisting of $n$ vertices and $m$ edges. Each edge connects two vertices. After a short time of research, she has realized that the graph may represents a special graph --  the $k$-th order Chiaki Chain.

An ordinary chain is a graph consisting of a sequential (at least two) vertices. Each two adjacent vertices are connected by an edge. The $k$-th order Chiaki Chain looks slightly different. There are $k$ sub-chains extended from the main chain from $k$ different vertices. At the end of each sub-chain, there is a simple cycle with length $3,4,\dots,k+2$. There is no useless vertices or edges in the $k$-th order Chiaki Chain.

Chiaki would like to know whether the graph represents the $k$-th order Chiaki Chain or not.

입력

There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:

The first line contains three integers $n$, $m$ and $k$ ($1 \le n,m, k \le 2 \times 10^5$) -- the number of vertices and the number of edges in the graph and the order of Chiaki Chain.

Then followed by $m$ lines, each line contains two integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le n$) representing the vertices the $i$-th edge connected.

It is guaranteed that the sum of $m$ in all test cases will not exceed $2 \times 10^5$.

출력

For each test case, output "Yes" if the graph represents the $k$-th order Chiaki Chain, or "No" if not.

예제 입력 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