Alice is the teacher of a class of students. She is going to divide the students into
groups. She has the following requirements:
- Alice knows that some pair of students are very good friends and they must not be assigned to the same group.
- Alice also wants to minimize the difference between the sizes of the two groups.
Let's write a program to help Alice to do the grouping, in which the program should:
- Report
-1
if it is not possible to do the grouping. - Report the group assigned to each student that fulfills the requirements.
Input Specification
- The first line contains two integers
and
, where
denotes the number of students, and
denotes the number of known relationships between students.
- Following are
lines, and each line contains two integers
and
, which means student
and
are very good friends and they must not be assigned to the same group. Each relationship will only be provided once.
Test cases
- In our test cases, we have
and
.
- In
of the test cases,
.
- In another
of the test cases, the number of possible ways to group students
.
Output Specification
- If there is no way to do the grouping, output
-1
. - Otherwise, output a string containing
characters representing the group assigned to each of the
students. If the
th student is assigned to group
, then the
th character in the string is
1
. Otherwise, theth character in the string is
2
. - The string should represent the grouping with minimum difference between the sizes of the two groups. (That is, the difference between the number of 1's and the number of 2's in the output should be minimized.) If there is a tie, output the lexicographically smallest solution.
Sample Input 1
4 3
1 2
3 4
1 3
Output for Sample Input 1
1221
Sample Input 2
3 3
1 2
1 3
2 3
Output for Sample Input 2
-1
Sample Input 3
6 4
1 2
1 3
4 6
4 5
Output for Sample Input 3
122211
Explanation
In Sample 1, since ,
and
cannot be assigned into the same group, to make the difference minimized, we want
and
be in the same group, and
and
be in the other. Among the outputs,
is lexicographically smallest. That is,
and
are in group
, and
and
are in group
.
In Sample 2, there is no way to do the grouping. The reason is that cannot be in the same group of
or
. But
and
cannot be in the same group, either.
In Sample 3, cannot be with
and
, and
cannot be with
and
. The minimized difference is
, by group
and
together.
Comments
Bro alice is a meanace, what teacher makes groups where no one are friends.