꼬불꼬불한 통로 timer 120s memory 1024MB

당신은 동굴을 조사하고 있다. 동굴에는 방이 \mathbf{N}개 있다. 방들 사이에는 일부 쌍을 양방향으로 연결하는 지하 통로(passages)가 존재한다. 각 방은 최소 하나의 통로와 연결되어 있다. 어떤 통로도 한 방에서 자기 자신으로 이어지지 않으며, 어떤 두 방도 두 개 이상의 통로로 연결되어 있지 않다.

어떤 방 안에 있을 때, 당신은 자신이 어떤 방에 있는지 식별할 수 있고 그 방이 몇 개의 통로와 연결되어 있는지도 알 수 있다. 하지만 통로들끼리는 구분할 수 없다. 당신은 동굴에 존재하는 통로의 총 개수를 추정하고 싶다. 당신은 최대 \mathbf{K}번의 연산을 수행할 수 있다. 한 번의 연산은 다음 둘 중 하나이다:

• 원하는 방으로 마법처럼 순간이동한다.
• 현재 방에 연결된 통로 중 하나를 "무작위"로 따라 걸어가, 그 통로의 반대편 방으로 이동한다.

통로를 따라 걷기로 결정했을 때, 당신은 어느 통로로 갈지 선택할 수 없다(모두 똑같이 생겼기 때문이다). 통로는 균등 무작위로 하나 선택된다.

당신은 임의의 방에서 조사를 시작한다. 최대 \mathbf{K}번의 연산만으로, 동굴의 방들 사이에 존재하는 통로의 개수를 추정하라.

추정값을 E, 실제 통로 수를 P라고 할 때, 해당 테스트 케이스에서 당신의 해답은 P \cdot 2/3 \le E \le P \cdot 4/3일 때 그리고 그때에만 정답으로 인정된다.

하나의 테스트 세트를 통과하려면, 그 테스트 세트의 테스트 케이스 중 적어도 90%에서 정답 판정을 받아야 한다.