시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 43 27 19 61.290%

문제

지구이는 “컴퓨터가 풀 수 없는 것이라면 사람도 풀 수 없다.”를 교훈으로 삼는 종교인 ‘튜링교’의 교주를 하고 있다. 이 종교는 포교 활동이 특히 심한 것으로 유명한데, 매일 여러 대학의 알고리즘 동아리에 무단침입을 하며, 그와 동시에 ‘링딩동’이나 ‘오로나민C’와 같은 중독성 심한 노래를 틀어 공부를 방해한다. (지구이는 이 노래를 트는 것이 포교활동의 효율을 올려주는 방법이라고 주장한다.)

도토리는 포교활동에 너무 큰 고통을 받았고(아직도 ‘링딩동’이 들리고 있는 것 같다고 한다), 결국 ‘튜링교’의 교휸을 깨기 위해 지구이에게 도전장을 보냈다. 도전장의 내용은 다음과 같다.

“친애하는 지구이 교주님. 강도 높은 포교활동을 줄이는 조건으로 내기를 합시다. 제가 문제 하나를 제시하면, 저는 그것을 손으로 풀고 교주님은 컴퓨터만을 사용해서 풀어서 먼저 푸는 쪽이 이기는 간단한 내기입니다. 제가 지면 튜링교에 들어가겠습니다. 도토리 드림“

이후 여러번의 연락 끝에 내기가 성사되었다. 도토리는 노력 끝에 NP 문제를 제시했고, 해킹을 통해 지구이의 코드를 알아내는 것에도 성공했으나, 아직 데이터를 만들지 못했다. 문제는 다음과 같다.

“정점 N(N ≤ 50)개, 간선 M(M ≤ N*(N-­1)/2)개가 주어졌을 때, 정점들을 간선으로 연결된 두 정점의 색이 항상 다르도록 4가지 색으로 색칠하여라. 단, 항상 조건을 만족하는 답이 하나 이상 존재한다.”

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

지구이 교주의 코드는 여기에 있다. 지구이 교주는 백트래킹 알고리즘으로 문제를 풀었다.

입력

입력은 없다.

출력

첫 번째 줄에 정점 수 N(2 ≤ N ≤ 50)과 간선 수 M (0 ≤ M ≤ N * (N­-1)/2)을 출력한다.

두 번째 줄부터 M개의 줄에 a, b (1 ≤ a, b ≤ N, a와 b는 다르다)를 출력한다.

중복간선은 허용하지 않는다.

m+2번째 줄에는 n개의 자연수 ci를 출력한다. (1 ≤ ci ≤ 4) ci는 i번째 정점의 색을 의미한다. 이 ci들은 문제의 조건을 만족해야한다.

출력 예시는 답이 아님에 주의하라.

예제 입력


예제 출력

4 5
1 2
1 3
1 4
2 3
2 4
1 2 3 4

힌트

출처

Contest > 꼬마컵 > 꼬마컵 2016 C번