베리 전투 timer 2s memory 1024MB

베리 따기는 힘든 일이지만, 평화롭고 마음이 편안해지는 경험이기도 합니다. 오랜 시간 동안 베리를 딴 후 잠자리에 들면 눈을 감았을 때 베리들만 보이는 경우가 많습니다. 당신의 마음이 무의식 속으로 빠져들면, 베리들이 스스로 삶을 살아가며 온갖 황당한 상황을 만들어낼 것입니다.

n개의 정점이 1부터 n까지 번호가 매겨진 트리가 주어집니다. 처음에는 각 정점에 하나의 베리가 있습니다. 또한 각 정점에는 그 베리를 지키는 개미가 하나씩 있습니다. 정점 v에서 베리를 따면, 다른 정점에 있는 모든 개미들이 v를 향해 한 걸음씩 걸어옵니다. 이미 v에 있는 개미들은 그 자리에 머뭅니다. 그래프가 트리이기 때문에, 개미들이 따라올 유일한 경로가 항상 존재합니다.

당신의 목표는 트리의 모든 베리를 따는 것입니다. 개미들이 분리되어 있는 한, 개미들은 당신에게 위험하지 않습니다. 그러나 어느 순간 모든 n개의 개미가 같은 정점에 모이게 되면, 그들은 당신을 공격할 것입니다. 개미들이 모두 같은 정점에 모이지 않도록 베리를 따는 순서를 찾아야 합니다.