{"raw_statement":[{"iden":"problem statement","content":"An undirected graph with numbered vertices is called a **good graph** if it has a spanning tree $T$ that satisfies the following condition. Here, an edge connecting two vertices $u$ and $v$ $(u < v)$ is denoted as edge $(u,v)$.\n\n*   For every edge $(u,v)$ $(u < v)$ in the graph, the minimum and maximum vertex numbers on the unique simple path connecting vertices $u$ and $v$ in $T$ are $u$ and $v$, respectively.\n\nYou are given a simple connected undirected graph $G$ with $N$ vertices numbered from $1$ to $N$. The graph $G$ has $M$ edges, and the $i$\\-th edge connects vertices $A_i$ and $B_i$ $(A_i < B_i)$.\nFor each $i=1,2,\\dots,M$, determine whether the graph obtained by removing the $i$\\-th edge from $G$ is a **good graph**."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 2 \\times 10^5$\n*   $N-1 \\leq M \\leq 2 \\times 10^5$\n*   $1 \\leq A_i < B_i \\leq N$\n*   All input values are integers.\n*   The given graph is a simple connected undirected graph."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $M$\n$A_1$ $B_1$\n$\\vdots$\n$A_M$ $B_M$"},{"iden":"sample input 1","content":"6 9\n1 3\n1 5\n2 5\n2 6\n3 4\n3 5\n3 6\n4 6\n5 6"},{"iden":"sample output 1","content":"No\nNo\nNo\nNo\nYes\nNo\nNo\nYes\nYes\n\nConsider the case where edge $(4,6)$ is removed. A spanning tree formed by edges $(1,3),(2,5),(3,4),(3,5),(5,6)$ satisfies the condition. For example, for edge $(3,6)$, the simple path connecting vertices $3$ and $6$ traverses vertices $3,5,6$ in this order, and the minimum and maximum vertex numbers on the path are $3$ and $6$, respectively, thus satisfying the condition. By verifying the other edges similarly, it can be seen that this spanning tree satisfies the condition, so the answer is `Yes`.\nOn the other hand, consider the case where edge $(1,5)$ is removed. The same spanning tree does not satisfy the condition. For edge $(4,6)$, the simple path connecting vertices $4$ and $6$ traverses vertices $4,3,5,6$ in this order, and the minimum and maximum vertex numbers on the path are $3$ and $6$, respectively, thus not satisfying the condition. It can also be shown that no other spanning tree satisfies the condition, so the answer is `No`."},{"iden":"sample input 2","content":"5 4\n1 2\n2 3\n3 4\n4 5"},{"iden":"sample output 2","content":"No\nNo\nNo\nNo\n\nRemoving an edge may disconnect the graph."},{"iden":"sample input 3","content":"15 20\n12 13\n7 8\n5 7\n8 10\n9 12\n4 5\n11 12\n2 4\n6 8\n4 14\n1 2\n14 15\n2 9\n3 8\n2 15\n10 11\n13 14\n8 9\n7 14\n5 13"},{"iden":"sample output 3","content":"No\nNo\nNo\nYes\nYes\nNo\nYes\nNo\nNo\nNo\nNo\nNo\nNo\nNo\nNo\nYes\nNo\nNo\nNo\nNo"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}