{"problem":{"name":"Pure","description":{"content":"Given is a directed graph $G$ with $N$ vertices and $M$ edges.   The vertices are numbered $1$ to $N$, and the $i$\\-th edge is directed from Vertex $A_i$ to Vertex $B_i$.   It is guaranteed that the g","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc142_f"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nInput 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$\n\n[samples]\n\n## Notes\n\nFor 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'$.","is_translate":false,"language":"English"}],"meta":{"iden":"abc142_f","tags":[],"sample_group":[["4 5\n1 2\n2 3\n2 4\n4 1\n4 3","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$."],["4 5\n1 2\n2 3\n2 4\n1 4\n4 3","\\-1\n\nThere is no induced subgraph of $G$ that satisfies the condition."],["6 9\n1 2\n2 3\n3 4\n4 5\n5 6\n5 1\n5 2\n6 1\n6 2","4\n2\n3\n4\n5"]],"created_at":"2026-03-03 11:01:14"}}