Group Division

Math teacher Maria plans to divide her students into two groups during the next lesson. So she now faces a common problem: how do you divide students into two groups in a sensible way? There are $n$ students in the class, and the classroom has $n$ chairs, numbered from $1$ to $n$. When a student arrives in the classroom, they always sit on the free chair that is furthest to the left. So if a total of $k$ people show up on a given day, they always sit on chairs $1, 2, \dots, k$.

To divide the students into two groups, Maria has a strategy she wants to use. Before the lesson starts, she chooses a sequence $s$ of $n$ ones and twos. When the lesson has started, she goes to each student and makes the student sitting on chair $i$ end up in group $s_i$. For the group division to be sensible, two requirements must hold for $s$:

1. Maria does not know how many students will come, but no matter how many show up, the difference in size between the two groups must be at most $1$.
2. There are $m$ pairs of chairs that have the same color. If students sit on such a pair of chairs, they must end up in the same group.

Your task is, given $n, m$ and the $m$ pairs of chairs, to find the sequence $s$ that comes first in alphabetical order and satisfies the requirements above. If there is no valid $s$, your program must print $-1$.

By alphabetical order we mean that two sequences are compared by first checking the first character, if it is the same checking the second, and so on. For example, the sequence 1122 comes before 1211, but after 1112.

The first line contains two integers $1 \le n \le 10^5$, the number of chairs in the classroom, and $0 \le m \le n/2$, the number of chair pairs with the same color. Then follow $m$ lines, each consisting of two integers, the pairs of chairs that have the same color (1-indexed). Each chair has the same color as at most one other chair.

Print a sequence of $n$ ones or twos (without spaces), or $-1$ if there is no valid solution.