위대한 달걀 찾기
시간 제한3초메모리 제한1024 MB
N개 방으로 이뤄진 트리에서 Egg First Search로 달걀을 찾는 기대 시간을 최소로 하는 시작 방을 모두 구합니다.
문제
매년 부활절에 Bob의 할머니는 가족 저택에서 The Great Egg Hunt를 연다. 이 행사는 Bob이 태어나기 전부터 이어져 온 가족 전통이다. 할머니는 먼저 커다란 부활절 달걀 안을 사탕으로 채운다. 그다음 방 하나를 균일한 확률로 무작위로 골라 달걀을 숨긴다. 달걀을 가장 먼저 찾은 사람이 그 안의 사탕을 모두 가진다.
저택에는 개의 방과 개의 문이 있으며, 각 문은 방 두 개를 잇는다. 저택은 연결되어 있어서, 문을 따라 어떤 방에서든 다른 모든 방으로 갈 수 있다.
Bob은 노련한 달걀 찾기 선수이며, Egg First Search라고 부르는 방법을 만들었다.
- Bob이 아직 탐색하지 않은 방에 있으면, 그 방을 탐색한다. Bob은 노련하므로 달걀이 그 방에 있으면 반드시 찾는다.
- 그렇지 않으면, Bob은 가장 가까운 미탐색 방이 있는 방향에 있는 인접한 방 중 하나로 이동한다. 그런 방이 여럿이면 균일한 확률로 무작위로 하나를 고른다.
방을 탐색하는 데 1 단위 시간이 걸리고, 인접한 방으로 이동하는 데도 1 단위 시간이 걸린다.
Bob은 탐색을 어느 방에서 시작할지 아직 정하지 못했다. 저택의 지도가 주어졌을 때, Egg First Search로 달걀을 찾는 기대 시간을 최소로 하는 시작 방을 모두 구하시오.
입력
첫 줄에 방의 개수를 나타내는 정수 ()이 주어진다. 이어지는 개의 줄에는 문으로 직접 연결된 방 한 쌍을 나타내는 공백으로 구분된 정수 와 (, )가 한 줄에 하나씩 주어진다. 저택이 연결되어 있다는 것은 보장된다.
출력
첫 줄에 최적의 시작 방의 개수 을 출력한다. 둘째 줄에는 최적의 시작 방 ()을 공백으로 구분하여 출력한다.