요원

어느 비밀 조직은 모든 요원을 팀에 배정해야 합니다. 일부 요원 쌍은 서로 함께 일할 수 없으므로, 같은 팀 안에 서로 싫어하는 요원 쌍이 들어가서는 안 됩니다. 임무의 특성상 요원은 최대 세 개의 팀으로만 나눌 수 있습니다.

조직에는 특별히 다루기 어려운 요원이 소수 존재합니다. 이런 요원은 최소 1명, 최대 3명이며, 나머지 모든 요원은 이들 중 적어도 한 명을 싫어합니다. 이러한 구조 덕분에 유효한 분할이 존재하는지 판정하는 문제는 항상 다항 시간에 풀 수 있습니다.

요원들과 서로 함께 일할 수 없는 쌍이 주어질 때, 같은 팀에 서로 싫어하는 쌍이 없도록 요원들을 최대 세 팀으로 나눌 수 있는지 판정하고, 가능하다면 그 배정을 출력하세요.

입력은 여러 개의 테스트 인스턴스로 구성됩니다.

각 인스턴스의 첫 줄에는 두 정수 $A$와 $R$가 공백으로 구분되어 주어집니다 ($1 \le A \le 500$, $0 \le R$). $A$는 요원의 수이며, 요원은 $0$부터 $A-1$까지 번호가 매겨집니다. $R$은 서로 싫어하는 요원 쌍의 수입니다. 이어지는 $R$개의 줄에는 각각 두 정수 $a_1$과 $a_2$가 주어지며 ($0 \le a_1, a_2 < A$), 이는 요원 $a_1$과 $a_2$가 서로 싫어함을 의미합니다. 서로 싫어하는 각 쌍은 정확히 한 번만 주어집니다.

각 인스턴스 뒤에는 빈 줄이 하나 옵니다. 입력은 두 개의 $0$이 적힌 줄로 끝납니다.

각 인스턴스마다 한 줄을 출력합니다.

같은 팀에 서로 싫어하는 쌍이 없도록 요원들을 최대 세 팀으로 나눌 수 있다면, 공백으로 구분된 $A$개의 정수를 출력합니다. $i$번째 정수($i$는 $0$부터 $A-1$까지)는 요원 $i$에게 배정된 팀 번호로 $\{0, 1, 2\}$ 중 하나입니다. 유효한 배정이 여러 개라면, 팀 번호 수열이 사전순으로 가장 앞서는 것을 출력합니다.

그러한 분할이 존재하지 않으면 문자열 The agents cannot be split을 출력합니다.