우나와 당신은 개의 별로 별자리를 만들려고 한다.
먼저 우나는 별자리를 만들기 위한 도안을 만든다. 도안은 개의 별을 정점으로 하는 무방향 그래프이며, 각 별에는 부터 까지 서로 다른 번호가 붙어 있다. 우나는 항상 다음 과정으로 도안을 만든다.
처음에는 별 하나만 존재한다. 이후 나머지 개의 별을 임의의 순서로 하나씩 추가한다. 별을 추가할 때마다 다음 두 방법 중 하나를 선택한다.
우나가 도안을 완성하면, 당신은 각 별 의 밝기 를 이상 이하의 정수로 정한다. 서로 다른 두 별 는
일 때, 그리고 그때에만 빛으로 연결된다.
빛으로 연결된 두 별을 간선으로 하는 그래프가 우나의 도안과 정확히 같아지도록 밝기 을 정하여라.
조건을 만족하는 밝기 배정이 항상 존재하는 입력만 주어진다.
입력은 다음과 같은 형식으로 주어진다.
각 테스트 케이스마다 조건을 만족하는 개의 정수 을 한 줄에 출력한다.
각 테스트 케이스는 다음과 같은 형식으로 주어진다.
각 는 별 와 별 를 잇는 간선을 나타낸다. 그래프에는 자기 자신을 잇는 간선과 중복 간선이 없다.
조건을 만족하는 답이 여러 개라면 그중 아무거나 출력해도 된다.
