제때 터지는 폭탄

안녕하십니까, 참가자. 게임을 하나 하겠습니다. 당신의 코치는 지금 대회장 안에 있고, 손에는 $T$초 뒤에 터지는 폭탄이 들려 있습니다. 폭탄이 대회장 안에서 터지면 당신 팀의 풍선만 모두 터집니다.

대회장이 있는 건물에는 방이 모두 $N$개 있습니다. 각 방에서는 다른 방으로 향하는 일방통행 터널이 정확히 하나씩 뻗어 있습니다. 예를 들어 $A$번 방이 $B$번 방으로 이어져 있으면 $A$에서 $B$로는 걸어갈 수 있지만, $B$에서 $A$로 향하는 터널이 따로 있지 않는 한 $B$에서 $A$로는 갈 수 없습니다.

폭탄에는 코치가 멈춰 서는 순간을 감지하는 장치가 달려 있어서, 멈추면 그 자리에서 즉시 터집니다. 그래서 코치는 쉬지 않고 방과 방 사이를 걸어 다니며, 터널 하나를 지나는 데 정확히 1초가 걸립니다. 코치는 대회장에서 출발하고, 각 방에서 나가는 터널이 하나뿐이므로 코치가 지나는 경로는 건물의 구조로 완전히 정해집니다. 풍선을 지키는 방법은 폭탄이 터지는 순간에 코치가 대회장에 있지 않게 하는 것뿐입니다.

건물의 지도는 알려 주지 않겠습니다. 알려 줄 수 있는 것은 터널이 균등한 확률로 무작위하게 정해졌다는 사실뿐입니다. 그 대신 $T$는 당신이 정할 수 있습니다. $T$는 $2$ 이상 $N$ 이하의 정수여야 합니다. 풍선이 살아남을 확률이 가장 커지도록 $T$를 고르십시오.

확률을 최대로 만드는 $T$는 하나뿐입니다.

그럼 게임을 시작하겠습니다.

첫째 줄에 건물의 방 개수 $N$이 주어진다. ($2 \le N \le 10^9$)

풍선이 살아남을 확률을 최대로 만드는 $T$를 한 줄에 출력한다.