그룹 나누기

수학 교사 Maria는 다음 수업 시간에 학생들을 두 그룹으로 나누려고 한다. 따라서 이제 그녀는 흔히 접하는 문제에 직면했다. 학생들을 어떻게 합리적으로 두 그룹으로 나눌 것인가? 반에는 $n$명의 학생이 있고, 교실에는 $1$부터 $n$까지 번호가 매겨진 $n$개의 의자가 있다. 학생이 교실에 도착하면 항상 비어 있는 의자 중 가장 왼쪽에 있는 의자에 앉는다. 따라서 어떤 날에 총 $k$명이 온다면, 이들은 항상 $1,2,...,k$번 의자에 앉게 된다.

학생들을 두 그룹으로 나누기 위해 Maria는 사용하고 싶은 전략이 있다. 수업이 시작되기 전에 그녀는 일과 이로 이루어진 길이 $n$의 수열 $s$을 선택한다. 수업이 시작되면 그녀는 각 학생에게 가서, $i$번 의자에 앉은 학생을 $s_i$번 그룹에 배정한다. 그룹을 합리적으로 나누려면 $s$이 충족해야 하는 두 가지 조건이 있다.

• Maria는 몇 명의 학생이 올지 모르지만, 몇 명이 오더라도 두 그룹의 크기 차이는 최대 $1$이어야 한다.

• 같은 색인 의자 쌍이 $m$개 있다. 그러한 의자 쌍에 학생들이 앉아 있다면, 그들은 같은 그룹에 배정되어야 한다.

주어진 $n,m$과 $m$개의 의자 쌍에 대해, 위 조건을 충족하면서 사전순으로 가장 앞서는 수열 $s$을 찾는 것이 과제이다. 유효한 $s$이 없다면 프로그램은 $-1$을 출력해야 한다.

사전순이란 두 수열을 비교할 때 먼저 첫 번째 문자를 확인하고, 같다면 두 번째 문자를 확인하는 식으로 계속하는 순서를 뜻한다. 예를 들어 수열 1122은 1211보다 앞서지만, 1112보다는 뒤에 온다.

점수

해답은 여러 테스트 케이스 그룹에 대해 채점된다. 한 그룹의 점수를 얻으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 배점 | 제한

$1$ |$12$| $n \leq 15$

$2$ |$23$| $n \leq 40$

$3$ |$25$| $i$번 의자는 $i\pm 1$번 의자와만 같은 색일 수 있다.

$4$ |$40$| 추가 제한이 없다.

첫 번째 줄에는 교실에 있는 의자의 수와 같은 색인 의자 쌍의 수를 나타내는 두 정수 $n$과 $m$가 주어진다. ($1\leq n \leq 10^5$, $0 \leq m \leq \frac{n}{2}$) 그다음 $m$개의 줄에 각각 두 정수 $s_{1}, s_{2}$가 주어진다. ($1 \leq s_{1}, s_{2} \leq N$, $s_{1} \neq s_{2}$) 이는 $s_{1}$번 의자와 $s_{2}$번 의자가 같은 색이라는 뜻이다. 각 의자는 최대 하나의 다른 의자와 같은 색이다.

일 또는 이로 이루어진 길이 $n$의 수열을 공백 없이 출력한다. 유효한 해가 없다면 $-1$을 출력한다.

두 명만 온다면 두 사람은 서로 다른 그룹에 속해야 한다. 따라서 $1$번 의자와 $2$번 의자는 서로 다른 그룹에 속해야 하지만, $3$번 의자는 $2$번 의자와 같은 그룹에 속해야 한다는 것도 알고 있다. 네 명이 온다면 두 그룹의 크기가 같아지도록 $4$번 의자는 $1$번 의자와 같은 그룹에 속해야 한다. 하지만 $4$번 의자는 $5$번 의자와 같은 그룹에 속해야 한다. 같은 방식으로 계속하면 $1, 4$번 의자와 $5$번 의자는 같은 그룹에 속해야 하고, $2, 3, 6$번 의자와 $7$번 의자는 다른 그룹에 속해야 함을 알 수 있다. 따라서 해는 $1221122$과 $2112211$의 두 가지이다. 이들 중 사전순으로 가장 작은 것은 $1221122$이다.