Score : $900$ points

Problem Statement

We define the density of a non-empty simple undirected graph as $\displaystyle\frac{(\text{number\ of\ edges})}{(\text{number\ of\ vertices})}$.

You are given positive integers $N$, $D$, and a simple undirected graph $G$ with $N$ vertices and $DN$ edges. The vertices of $G$ are numbered from $1$ to $N$, and the $i$-th edge connects vertex $A_i$ and vertex $B_i$. Determine whether $G$ satisfies the following condition.

Condition: Let $V$ be the vertex set of $G$. For any non-empty proper subset $X$ of $V$, the density of the induced subgraph of $G$ by $X$ is strictly less than $D$.

There are $T$ test cases to solve.

Constraints

• $T \geq 1$
• $N \geq 1$
• $D \geq 1$
• The sum of $DN$ over the test cases in each input file is at most $5 \times 10^4$.
• $1 \leq A_i < B_i \leq N \ \ (1 \leq i \leq DN)$
• $(A_i, B_i) \neq (A_j, B_j) \ \ (1 \leq i < j \leq DN)$

Input

The input is given from Standard Input in the following format:

$T$

$\mathrm{case}_1$

$\mathrm{case}_2$

$\vdots$

$\mathrm{case}_T$

Each test case $\mathrm{case}_i \ (1 \leq i \leq T)$ is in the following format:

$N$ $D$

$A_1$ $B_1$

$A_2$ $B_2$

$\vdots$

$A_{DN}$ $B_{DN}$

Output

Print $T$ lines. The $i$-th line should contain Yes if the given graph $G$ for the $i$-th test case satisfies the condition, and No otherwise.

2
3 1
1 2
1 3
2 3
4 1
1 2
1 3
2 3
3 4

Yes
No

• The first test case is the same as Sample Input 1 in Problem D

  , and it satisfies the condition.

• For the second test case, the edge set of the induced subgraph by the non-empty proper subset $\{1, 2, 3\}$ of the vertex set $\{1, 2, 3, 4\}$ is $\{(1, 2), (1, 3), (2, 3)\}$, and its density is $\displaystyle\frac{3}{3} = 1 = D$. Therefore, this graph does not satisfy the condition.