후공으로 이기기 timer 60s memory 1024MB

율리(Ueli)와 브레니(Vreni)가 게임을 하고 있다. 게임판은 꼭짓점이 \mathbf{N}개인 트리이며, 모든 꼭짓점은 처음에 파란색으로 칠해져 있다. 두 사람은 번갈아 가며 턴을 진행하고, 율리가 먼저 시작한다. 각 턴에서 플레이어는 파란색 꼭짓점 하나를 고르고, 그 꼭짓점과 인접한(이웃인) 파란색 꼭짓점들 중 임의의 부분집합(없어도 되고 전부여도 된다)을 함께 골라, 선택된 모든 꼭짓점을 빨간색으로 칠해야 한다. 어떤 플레이어의 턴이 시작될 때 모든 꼭짓점이 이미 빨간색이라면, 그 플레이어가 게임에서 지고 다른 플레이어가 이긴다.

아래 예시 게임에서, 율리는 첫 턴에 꼭짓점 3을 빨간색으로 칠했다. 그 다음 브레니는 자신의 턴에서 꼭짓점 2를 골라, 그것과 이웃 꼭짓점(꼭짓점 1)을 함께 빨간색으로 칠했다. 이제 모든 꼭짓점이 빨간색이 되었으므로, 율리가 지고 브레니가 이긴다.

율리와 브레니는 율리가 선공이기 때문에 이 게임에서 율리가 이기기 훨씬 쉽다는 것을 알아차렸다. 그래서 다음과 같은 절차를 도입했다. 먼저 율리가 정수 \mathbf{N}을 선택한다. 그러면 브레니가 꼭짓점이 \mathbf{N}개인 임의의 트리 하나를 선택한다. 그 다음, 위에서 설명한 규칙대로 게임을 시작하되, 율리가 먼저 턴을 가진다.

브레니는 트리를 선택할 수 있다면 후공의 불리함을 극복할 수 있기를 바라고 있다. 이 설정에서 브레니가 이길 수 있는 방법을 보여 줄 수 있는가?