{"raw_statement":[{"iden":"problem statement","content":"There is a simple connected undirected graph $G$ with $N$ vertices and $M$ edges, where the vertices are labeled $1,2,\\dots,N$. The $i$\\-th edge connects two vertices $u_i$ and $v_i$.\nDetermine whether there exists a length-$N$ sequence of non-negative integers $X=(X_1,X_2,\\dots,X_N)$ that satisfies all of the following conditions:\n\n*   $X_v$ does not exceed the degree of vertex $v$ in $G$ for each $v=1,2,\\dots,N$.\n*   There is **no** directed graph obtained by assigning directions to the $M$ edges of $G$ in which, for each $v=1,2,\\dots,N$, either the in-degree or the out-degree of $v$ equals $X_v$.\n\nYou have $T$ test cases; solve each of them."},{"iden":"constraints","content":"*   $1 \\leq T \\leq 10^5$\n*   $2 \\leq N \\leq 2 \\times 10^5$\n*   $N-1 \\leq M \\leq 2 \\times 10^5$\n*   $1 \\leq u_i, v_i \\leq N$\n*   All input values are integers.\n*   The graph $G$ given in the input is a simple connected undirected graph.\n*   The sum of $N$ over all test cases in each input is at most $2 \\times 10^5$.\n*   The sum of $M$ over all test cases in each input is at most $2 \\times 10^5$."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$T$\n$\\mathrm{case}_1$\n$\\vdots$\n$\\mathrm{case}_T$\n\nEach case is given in the following format:\n\n$N$ $M$\n$u_1$ $v_1$\n$u_2$ $v_2$\n$\\vdots$\n$u_M$ $v_M$"},{"iden":"sample input 1","content":"3\n4 4\n1 2\n2 3\n3 4\n4 1\n7 6\n3 4\n3 6\n2 5\n1 2\n1 3\n2 7\n15 20\n11 13\n11 7\n12 6\n5 2\n4 1\n15 3\n9 8\n13 5\n8 6\n7 5\n11 8\n12 9\n14 1\n1 11\n6 7\n1 3\n2 3\n3 7\n5 12\n10 6"},{"iden":"sample output 1","content":"Yes\nNo\nYes\n\nIn the first test case, for example, $X=(2,2,2,1)$ satisfies the conditions.\nIn the second test case, no sequence $X$ satisfies the conditions."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}