{"raw_statement":[{"iden":"problem statement","content":"We have two sequences $A_1,\\ldots, A_M$ and $B_1,\\ldots,B_M$ consisting of intgers between $1$ and $N$ (inclusive).\nFor a string of length $M$ consisting of `0` and `1`, consider the following undirected graph with $2N$ vertices and $(M+N)$ edges corresponding to that string.\n\n*   If the $i$\\-th character of the string is `0`, the $i$\\-th edge connects Vertex $A_i$ and Vertex $(B_i+N)$.\n*   If the $i$\\-th character of the string is `1`, the $i$\\-th edge connects Vertex $B_i$ and Vertex $(A_i+N)$.\n*   The $(j+M)$\\-th edge connects Vertex $j$ and Vertex $(j+N)$.\n\nHere, $i$ and $j$ are integers such that $1 \\leq i \\leq M$ and $1 \\leq j \\leq N$, and the vertices are numbered $1$ to $2N$.\nFind one string of length $M$ consisting of `0` and `1` such that the corresponding undirected graph has the minimum number of bridges.\nNotes on bridges A bridge is an edge of a graph whose removal increases the number of connected components."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq M \\leq 2 \\times 10^5$\n*   $1 \\leq A_i, B_i \\leq N$"},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $M$\n$A_1$ $A_2$ $\\cdots$ $A_M$\n$B_1$ $B_2$ $\\cdots$ $B_M$"},{"iden":"sample input 1","content":"2 2\n1 1\n2 2"},{"iden":"sample output 1","content":"01\n\nThe graph corresponding to `01` has no bridges.\nIn the graph corresponding to `00`, the edge connecting Vertex $1$ and Vertex $3$ and the edge connecting Vertex $2$ and Vertex $4$ are bridges, so `00` does not satisfy the requirement."},{"iden":"sample input 2","content":"6 7\n1 1 2 3 4 4 5\n2 3 3 4 5 6 6"},{"iden":"sample output 2","content":"0100010"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}