{"raw_statement":[{"iden":"problem statement","content":"Given is a directed graph $G$ with $N$ vertices and $M$ edges.  \nThe vertices are numbered $1$ to $N$, and the $i$\\-th edge is directed from Vertex $A_i$ to Vertex $B_i$.  \nIt is guaranteed that the graph contains no self-loops or multiple edges.\nDetermine whether there exists an induced subgraph (see Notes) of $G$ such that the in-degree and out-degree of every vertex are both $1$. If the answer is yes, show one such subgraph.  \nHere the null graph is not considered as a subgraph."},{"iden":"notes","content":"For a directed graph $G = (V, E)$, we call a directed graph $G' = (V', E')$ satisfying the following conditions an induced subgraph of $G$:\n\n*   $V'$ is a (non-empty) subset of $V$.\n*   $E'$ is the set of all the edges in $E$ that have both endpoints in $V'$."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 1000$\n*   $0 \\leq M \\leq 2000$\n*   $1 \\leq A_i,B_i \\leq N$\n*   $A_i \\neq B_i$\n*   All pairs $(A_i, B_i)$ are distinct.\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $M$\n$A_1$ $B_1$\n$A_2$ $B_2$\n$:$\n$A_M$ $B_M$"},{"iden":"sample input 1","content":"4 5\n1 2\n2 3\n2 4\n4 1\n4 3"},{"iden":"sample output 1","content":"3\n1\n2\n4\n\nThe induced subgraph of $G$ whose vertex set is ${1, 2, 4}$ has the edge set ${(1, 2), (2, 4), (4, 1)}$. The in-degree and out-degree of every vertex in this graph are both $1$."},{"iden":"sample input 2","content":"4 5\n1 2\n2 3\n2 4\n1 4\n4 3"},{"iden":"sample output 2","content":"\\-1\n\nThere is no induced subgraph of $G$ that satisfies the condition."},{"iden":"sample input 3","content":"6 9\n1 2\n2 3\n3 4\n4 5\n5 6\n5 1\n5 2\n6 1\n6 2"},{"iden":"sample output 3","content":"4\n2\n3\n4\n5"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}