{"problem":{"name":"Everywhere is Sparser than Whole (Judge)","description":{"content":"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 sim","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":8000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc161_f"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $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)$\n\n## Input\n\nThe 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}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc161_f","tags":[],"sample_group":[["2\n3 1\n1 2\n1 3\n2 3\n4 1\n1 2\n1 3\n2 3\n3 4","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."]],"created_at":"2026-03-03 11:01:14"}}