보물찾기

여러분은 해적과 그들의 보물에 대해 들어 본 적이 있나요? Bytie는 Gdynia 해변을 걷다가 낡은 병을 발견했다. 병 안의 편지에는 숨겨진 보물을 찾는 방법이 적혀 있지만, 해독하기가 꽤 어렵다. Bytie가 확실히 아는 것은 근처 공원에서 특별한 두 점을 찾아야 하고, 보물은 그 두 점을 잇는 경로의 한가운데에 있다는 것이다.

공원에는 여러 개의 산책로가 있다. 숲이 매우 빽빽해서 사람은 산책로 위의 위치에만 도달할 수 있다. 산책로의 구조에는 흥미로운 성질이 있다. 산책로 위의 임의의 두 점을 잇는 경로는 유일하게 존재한다. 경로는 여러 산책로를 따라갈 수 있지만, 같은 점을 두 번 방문하지 않는다.

Bytie는 친구들에게 공원 탐사를 도와 달라고 부탁했다. 친구들은 산책로 위의 한 점에서 보물찾기를 시작한다. 탐사는 여러 단계로 진행된다. 각 단계에서 친구 한 명이 이미 탐사한 점을 골라, 그 점에서 산책로를 따라 일정한 걸음 수만큼 걷는다. 이때 방문하는 점은 어느 친구도 이전에 도달하지 않은 점이어야 한다.

탐사하는 동안 Bytie는 공원의 구조를 자세히 분석한다. 가끔 Bytie는 보물의 위치를 정하는 두 특별한 점을 추측할 수 있다. 추측할 때마다 그 두 점을 잇는 유일한 경로의 가운데 점을 알고 싶어 한다. 여러분의 과제는 이 가운데 점들을 구하는 것이다.

함수 init, path, dig의 호출은 최대 400 000번이며, Bytie의 친구들이 탐사하는 점은 최대 1 000 000 000개다.