지도 색칠하기

아주 먼 옛날 아주 먼 은하계에 지도 제작소가 있었다. 젊은 제도사 닉은 자기 세계의 첫 지도를 만들려고 한다. 커다란 종이 한 장에 나라의 경계선을 모두 그린 다음, 지도를 보기 좋게 만들려고 나라마다 색을 칠하기로 했다. 한 나라는 한 가지 색으로만 칠하고, 국경을 맞댄 두 나라는 서로 다른 색이어야 한다.

문제는 닉에게 색연필이 파랑, 갈색, 초록, 빨강, 노랑 다섯 자루뿐이라는 것이다. 색연필에는 1번부터 5번까지 번호가 붙어 있다.

닉은 칠하는 순서를 절대 바꾸지 않는다. 1번 나라부터 N번 나라까지 번호 순서대로 칠하고, 나라 i를 칠할 때는 이미 칠해 둔 이웃 나라가 하나도 쓰지 않은 색연필 중에서 번호가 가장 작은 것을 고른다. 아직 칠하지 않은 이웃은 보지 않는다. 이미 칠한 이웃이 다섯 자루를 모두 쓰고 있으면 닉은 그 나라에서 포기한다.

닉이 칠한 결과를 구하라. 지도는 직사각형 종이에 그려져 있고, 각 나라는 연결된 하나의 영역이며, 두 나라가 겹치는 일은 없다.

첫째 줄에 두 정수 N과 M이 주어진다 (1 ≤ N ≤ 200,000). N은 나라의 수, M은 국경을 맞댄 나라 쌍의 수다. 나라에는 1번부터 N번까지 번호가 붙어 있다.

다음 M개 줄에는 각각 두 정수 A와 B가 주어진다 (1 ≤ A, B ≤ N). 나라 A와 나라 B가 국경을 맞대고 있다는 뜻이다. 국경을 맞댄 나라 쌍은 정확히 한 번씩만 주어진다.

닉이 마지막 나라까지 칠했다면 첫째 줄에 N개의 수를 공백 하나로 구분해 출력한다. i번째 수 Ci (1 ≤ Ci ≤ 5)는 나라 i에 칠한 색연필 번호다.

닉이 도중에 포기했다면 첫째 줄에 It is not possible .만 출력한다. 마침표 앞의 공백까지 그대로 출력해야 한다.