문제

- 호드와 얼라이언스, 둘 다 내게 무엇을 해주었지?

이웃랜드의 유명한 도적, 빌리라 생귀나르는 이제로스의 도시들에 보물이 숨겨져 있다는 사실을 입수했다. 빌리라의 목적은 모든 도시에 있는 보물을 훔치는 것이다. 이를 위해, 빌리라는 모든 도시를 한 번 이상 방문하기로 했다.

이제로스에는 N개의 도시가 있다. 도시들은 두 도시를 잇는 도로들로 연결되어 있다. 모든 도시들은 총 N-1개의 도로를 통해 연결되어 있으며, 어떤 두 도시를 선택해도 도로들을 통해서 연결되어 있다. 이제로스의 도시들은 사람들이 한곳에 몰리는 것을 방지하기 위해, 한 도시는 최대 세 개의 도로만 인접하도록 설계되어있다.

이러한 빌리라의 움직임을 예상한 주술사 스릴은, 이웃랜드의 도시에 서리늑대 부족 경비원들을 배치했다. 경비원은 시작도시로부터 정해진 목적도시로 이동하며 도착하면 그 즉시 다시 시작도시로 돌아오는 이동하기를 반복한다. 즉 할당된 두 도시를 계속 왕복하며 이동한다. 만약 빌리라와 서리늑대 부족 경비원이 동시에 같은 도로를 지나게 된다면, 빌리라는 잡혀서 감옥에 들어가게 될 것이다. 그러나 도시에서는 빌리라가 몸을 숨길 수 있어 빌리라와 경비원이 같은 도시에 있더라도 잡혀가지 않는다. 빌리라는 하루에 최대 하나의 도로를 지날 수 있으며, 서리늑대 부족 경비원들은 항상 하루에 하나의 도로를 지난다.

스릴은 한 명의 경비원이 너무 많은 도로를 감시하게 되는 것을 원치 않는다. 그래서 한 경비원이 최대 11개의 도로만 지나도록 배치하였다. (즉, 모든 경비원은 각각 시작도시와 목적도시 사이에 최대 11개의 도로만 있게 된다.)

다행히 빌리라는 스릴의 서리늑대 부족 경비원 배치상황을 알아낼 수 있었다. 이 경비원 배치자료를 토대로 빌리라는 당신에게 가장 빠르게 모든 도시를 방문하는 계획을 세워달라고 부탁했다. 빌리라는 모든 도시를 방문하기 위해 최소 며칠이 필요할까?