빠른 이동 색칠
시간 제한2초메모리 제한256 MB
7n개 정점으로 이루어진 완전 그래프의 간선을 n가지 색으로 칠합니다. 모든 정점 쌍은 각 색마다 직접 같은 색 간선으로 이어지거나 같은 색 두 간선으로 연결되어야 합니다.
문제
정점이 개인 완전 무방향 그래프가 주어진다. 은 양의 정수이다. 이 그래프의 간선을 가지 색으로 칠하라. 모든 정점 쌍 와 모든 색 에 대해 다음 중 적어도 하나가 성립해야 한다.
- 정점 와 를 잇는 간선의 색이 이다.
- 간선 와 의 색이 모두 인 정점 가 존재한다.
입력
양의 정수 이 한 줄에 주어진다. ()
출력
색에 1부터 까지 번호를 붙인다. 이면 으로 두고, 그렇지 않으면 를 간선 의 색으로 한다(). 를 줄에 걸쳐 각 줄마다 개의 수로 출력한다.
해가 존재함이 보장된다.
힌트
두 번째 예제는 다음 색칠에 해당한다. 아래 두 그림은 각 색의 부분 그래프를 보여 준다.
