{"raw_statement":[{"iden":"problem statement","content":"There is an integer sequence $x = (x_1, \\ldots, x_N)$, which is initialized with $x_1 = \\cdots = x_N = 0$.\nYou will perform $M$ operations on this integer sequence. In the $i$\\-th operation, you are given an integer pair $(L_i, R_i)$ such that $1 \\leq L_i \\leq R_i \\leq N$, and you must perform **exactly one** of the following three operations:\n\n*   Operation $0$: Do nothing. This operation incurs a cost of $0$.\n*   Operation $1$: For each integer $j$ with $1 \\leq j \\leq N$, if $L_i \\leq j \\leq R_i$ **holds**, set $x_j = 1$. This operation incurs a cost of $1$.\n*   Operation $2$: For each integer $j$ with $1 \\leq j \\leq N$, if $L_i \\leq j \\leq R_i$ **does not hold**, set $x_j = 1$. This operation incurs a cost of $1$.\n\nYour goal is to make $x_1 = \\cdots = x_N = 1$ hold at the end. Determine whether this goal can be achieved. If it can be achieved, present one way to achieve it where the total cost of the operations is minimized."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 1000000$\n*   $1 \\leq M \\leq 200000$\n*   $1 \\leq L_i \\leq R_i \\leq N$\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $M$\n$L_1$ $R_1$\n$\\vdots$\n$L_M$ $R_M$"},{"iden":"sample input 1","content":"5 4\n2 4\n3 5\n1 4\n2 5"},{"iden":"sample output 1","content":"2\n2 0 1 0\n\nIn the sample output, $x$ changes as follows:\n\n*   Initially, $x = (0,0,0,0,0)$.\n*   In the 1st operation, Operation $2$ is performed. $x_1$ and $x_5$ become 1, so $x = (1,0,0,0,1)$.\n*   In the 2nd operation, Operation $0$ is performed. $x$ remains $(1,0,0,0,1)$.\n*   In the 3rd operation, Operation $1$ is performed. $x_1, x_2, x_3, x_4$ become 1, so $x = (1,1,1,1,1)$.\n*   In the 4th operation, Operation $0$ is performed. $x$ remains $(1,1,1,1,1)$."},{"iden":"sample input 2","content":"5 4\n1 3\n1 5\n2 4\n3 5"},{"iden":"sample output 2","content":"1\n0 1 0 0"},{"iden":"sample input 3","content":"5 2\n1 3\n2 5"},{"iden":"sample output 3","content":"2\n1 1"},{"iden":"sample input 4","content":"5 2\n1 3\n2 4"},{"iden":"sample output 4","content":"\\-1"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}