{"raw_statement":[{"iden":"problem statement","content":"We have a simple undirected graph $G$ with $(S+T)$ vertices and $M$ edges. The vertices are numbered $1$ through $(S+T)$, and the edges are numbered $1$ through $M$. Edge $i$ connects Vertices $u_i$ and $v_i$.  \nHere, vertex sets $V_1 = \\lbrace 1, 2,\\dots, S\\rbrace$ and $V_2 = \\lbrace S+1, S+2, \\dots, S+T \\rbrace$ are both independent sets.\nA cycle of length $4$ is called a 4-cycle.  \nIf $G$ contains a 4-cycle, choose any of them and print the vertices in the cycle. You may print the vertices in any order.  \nIf $G$ does not contain a 4-cycle, print `-1`.\nWhat is an independent set? An independent set of a graph $G$ is a set $V'$ of some of the vertices in $G$ such that no two vertices of $V'$ have an edge between them."},{"iden":"constraints","content":"*   $2 \\leq S \\leq 3 \\times 10^5$\n*   $2 \\leq T \\leq 3000$\n*   $4 \\leq M \\leq \\min(S \\times T,3 \\times 10^5)$\n*   $1 \\leq u_i \\leq S$\n*   $S + 1 \\leq v_i \\leq S + T$\n*   If $i \\neq j$, then $(u_i, v_i) \\neq (u_j, v_j)$.\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$S$ $T$ $M$\n$u_1$ $v_1$\n$u_2$ $v_2$\n$\\vdots$\n$u_M$ $v_M$"},{"iden":"sample input 1","content":"2 3 5\n1 3\n1 4\n1 5\n2 4\n2 5"},{"iden":"sample output 1","content":"1 2 4 5\n\nThere are edges between Vertices $1$ and $4$, $4$ and $2$, $2$ and $5$, and $5$ and $1$, so Vertices $1$, $2$, $4$, and $5$ form a 4-cycle. Thus, $1$, $2$, $4$, and $5$ should be printed.  \nThe vertices may be printed in any order. Besides the Sample Output, `2 5 1 4` is also considered correct, for example."},{"iden":"sample input 2","content":"3 2 4\n1 4\n1 5\n2 5\n3 5"},{"iden":"sample output 2","content":"\\-1\n\nSome inputs may give $G$ without a 4-cycle."},{"iden":"sample input 3","content":"4 5 9\n3 5\n1 8\n3 7\n1 9\n4 6\n2 7\n4 8\n1 7\n2 9"},{"iden":"sample output 3","content":"1 7 2 9"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}