Agents

A secret organization must assign every one of its agents to a team. Some pairs of agents cannot work together, so no team may contain a pair of agents who dislike each other. Because of the nature of the mission, the agents can be divided into at most three teams.

The organization has a few especially difficult members — at least one and at most three of them — and every other agent dislikes at least one of these difficult members. Thanks to this structure, deciding whether a valid division exists is always solvable in polynomial time.

Given the agents and the pairs who cannot work together, decide whether the agents can be split into at most three teams so that no team contains a disliking pair, and if so, report the assignment.

The input consists of several test instances.

The first line of each instance contains two integers $A$ and $R$ ($1 \le A \le 500$, $0 \le R$), separated by a space. $A$ is the number of agents, numbered from $0$ to $A-1$, and $R$ is the number of pairs of agents who dislike each other. Each of the next $R$ lines contains two integers $a_1$ and $a_2$ ($0 \le a_1, a_2 < A$), meaning that agents $a_1$ and $a_2$ dislike each other. Each such pair is listed exactly once.

A blank line follows each instance. The input ends with a line containing two zeros.

For each instance, print one line.

If the agents can be split into at most three teams so that no team contains a pair who dislike each other, print $A$ integers separated by single spaces: the $i$-th integer (for $i$ from $0$ to $A-1$) is the team number in $\{0, 1, 2\}$ assigned to agent $i$. Among all valid assignments, print the lexicographically smallest sequence of team numbers.

If no such division exists, print the string The agents cannot be split.