{"raw_statement":[{"iden":"problem statement","content":"We define the **density** of a non-empty simple undirected graph as $\\displaystyle\\frac{(\\text{number\\ of\\ edges})}{(\\text{number\\ of\\ vertices})}$.\nYou 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.\n**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$.\nThere are $T$ test cases to solve.\n\nWhat is an induced subgraph?\n\nFor a vertex subset $X$ of graph $G$, the **induced subgraph** of $G$ by $X$ is the graph with vertex set $X$ and edge set containing all edges of $G$ that connect two vertices in $X$. In the above condition, note that we only consider vertex subsets that are neither empty nor the entire set."},{"iden":"constraints","content":"*   $T \\geq 1$\n*   $N \\geq 1$\n*   $D \\geq 1$\n*   The sum of $DN$ over the test cases in each input file is at most $5 \\times 10^4$.\n*   $1 \\leq A_i < B_i \\leq N \\ \\ (1 \\leq i \\leq DN)$\n*   $(A_i, B_i) \\neq (A_j, B_j) \\ \\ (1 \\leq i < j \\leq DN)$"},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$T$\n$\\mathrm{case}_1$\n$\\mathrm{case}_2$\n$\\vdots$\n$\\mathrm{case}_T$\n\nEach test case $\\mathrm{case}_i \\ (1 \\leq i \\leq T)$ is in the following format:\n\n$N$ $D$\n$A_1$ $B_1$\n$A_2$ $B_2$\n$\\vdots$\n$A_{DN}$ $B_{DN}$"},{"iden":"sample input 1","content":"2\n3 1\n1 2\n1 3\n2 3\n4 1\n1 2\n1 3\n2 3\n3 4"},{"iden":"sample output 1","content":"Yes\nNo\n\n*   The first test case is the same as Sample Input 1 in [Problem D](./arc161_d), and it satisfies the condition.\n*   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."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}