그룹 나누기

수학 선생님 마리아는 다음 수업에서 학생들을 두 그룹으로 나누려고 한다. 그래서 그녀는 흔한 문제에 부딪힌다. 학생들을 어떻게 하면 합리적으로 두 그룹으로 나눌 수 있을까? 교실에는 $n$명의 학생이 있고, 교실에는 $1$번부터 $n$번까지 번호가 붙은 $n$개의 의자가 있다. 학생이 교실에 도착하면 항상 가장 왼쪽에 있는 빈 의자에 앉는다. 따라서 어떤 날에 총 $k$명이 오면 그들은 항상 $1, 2, \dots, k$번 의자에 앉는다.

마리아는 학생들을 두 그룹으로 나누기 위해 사용하고 싶은 전략이 있다. 수업이 시작하기 전에 그녀는 $n$개의 1과 2로 이루어진 수열 $s$를 고른다. 수업이 시작되면 그녀는 각 학생에게 다가가서 $i$번 의자에 앉은 학생이 $s_i$번 그룹에 속하게 한다. 그룹 나누기가 합리적이려면 $s$가 다음 두 조건을 만족해야 한다.

1. 마리아는 몇 명의 학생이 올지 모르지만, 몇 명이 오든 두 그룹의 크기 차이는 $1$ 이하여야 한다.
2. 같은 색을 가진 의자 쌍이 $m$개 있다. 그러한 의자 쌍에 학생이 앉아 있으면 그 학생들은 같은 그룹에 속해야 한다.

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

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

첫 번째 줄에는 두 정수 $1 \le n \le 10^5$ (교실의 의자 수)와 $0 \le m \le n/2$ (같은 색을 가진 의자 쌍의 수)가 주어진다. 그다음 $m$개의 줄이 주어지며, 각 줄에는 같은 색을 가진 의자 쌍을 나타내는 두 정수가 1부터 시작하는 번호로 주어진다. 각 의자는 최대 하나의 다른 의자와 같은 색을 가진다.

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