네트워크 구성
시간 제한2초메모리 제한256 MB
트리가 주어질 때, 모든 정점을 거리 벡터로 유일하게 구분하는 최소 개수의 정점을 찾아 그 집합을 출력한다.
문제
어느 진보적인 나라에서 정보 기술 발전이 한창이다. 데이터 전송에 사용할 간선들이 빠른 속도로 놓였다. 데이터 흐름을 관리하기 쉽게 하고 간선 설치 비용을 아끼기 위해, 간선은 어느 도시에서든 다른 어느 도시로든 데이터가 유일한 경로로 도달할 수 있도록 설치되었다.
하지만 전선을 설치하는 것만으로는 부족하고, 라우팅 알고리즘도 설계해야 한다. 논의 과정에서 다음과 같은 데이터 라우팅 모델이 나왔다. k개의 도시를 핵심 지점으로 지정하고, 각각의 이름을 "서버그라드-i"로 바꾼다. 그런 다음 각 도시는 네트워크 주소를 받는다. 도시 v의 네트워크 주소는 k개의 원소로 이루어진 배열이고, i번째 원소는 도시 v에서 서버그라드-i로 트래픽이 이동할 때 거쳐야 하는 도시의 수이다.
라우팅에 문제가 없으려면 모든 도시가 서로 다른 주소를 가져야 한다. 또한 정부는 서버그라드의 수가 가능한 한 적기를 바란다. 어떤 도시를 서버그라드로 지정할지 정부를 도와라.
입력
첫째 줄에 나라의 도시 수 n이 주어진다(2 ≤ n ≤ 100 000). 다음 n - 1개 줄에 간선으로 연결된 두 도시의 쌍이 주어진다.
출력
모든 도시의 라우팅이 올바르게 이루어지도록 하는 최소 서버그라드 수 k를 출력한다. 이어서 1부터 n까지의 서로 다른 정수 k개를 출력하는데, i번째 수는 서버그라드-i로 선택할 도시를 나타낸다.