손은 컴퓨터보다 빠르다

지구이는 "컴퓨터가 풀 수 없는 것이라면 사람도 풀 수 없다."를 교훈으로 삼는 종교 튜링교의 교주이다. 이 종교는 포교가 특히 심하다. 매일 여러 대학의 알고리즘 동아리에 무단으로 들어가고 그와 동시에 링딩동이나 오로나민C처럼 중독성이 강한 노래를 틀어 공부를 방해한다. 지구이는 이 노래를 트는 것이 포교 효율을 올린다고 주장한다.

도토리는 포교에 너무 큰 고통을 받았다. 아직도 링딩동이 들리는 것 같다고 한다. 결국 튜링교의 교훈을 깨려고 지구이에게 도전장을 보냈다. 도전장의 내용은 다음과 같다.

"친애하는 지구이 교주님. 강도 높은 포교를 줄이는 조건으로 내기를 합시다. 제가 문제 하나를 제시하면 저는 손으로 풀고 교주님은 컴퓨터만 써서 풉니다. 먼저 푸는 쪽이 이깁니다. 제가 지면 튜링교에 들어가겠습니다. 도토리 드림"

이후 여러 번 연락한 끝에 내기가 성사되었다. 도토리가 낸 문제는 그래프를 네 가지 색으로 칠하는 것이다. 인접한 두 정점의 색은 달라야 한다.

원래 출제에서는 정점 수와 간선 목록과 올바른 4-색칠을 아무거나 출력해도 되었다. 이 문제에서는 그래프와 색칠을 하나로 고정한다.

정점은 $4$개이다. 간선은 $1 \le a < b \le 4$인 쌍 가운데 $\{3, 4\}$만 뺀 $5$개이다. 간선은 $a$가 오름차순, $a$가 같으면 $b$가 오름차순이 되도록 출력한다. 정점 $i$의 색은 $i$이다. 빠진 간선이 $\{3, 4\}$뿐이므로 인접한 정점의 색은 모두 다르다.

도토리가 튜링교에 끌려가지 않도록 도와주자.

입력이 없다.

첫 번째 줄에 정점 수 $N$과 간선 수 $M$을 출력한다. $N$은 $4$이고 $M$은 $5$이다.

다음 $5$개의 줄에 간선 끝점 $a$와 $b$를 공백으로 구분해 출력한다. 순서는 $1$ $2$, $1$ $3$, $1$ $4$, $2$ $3$, $2$ $4$이다. 중복 간선은 없다.

그다음 줄에 정점 $1$부터 $4$까지의 색 $c_i$를 공백으로 구분해 출력한다. 값은 $1$ $2$ $3$ $4$이다.