마법 쇼

앨리스와 밥은 유명한 마술사이다. 그들의 놀라운 기술에 관심을 보인 부유한 여성 캐서린은 두 사람이 다음 마술을 성공하면 막대한 재산을 주겠다고 선언했다. 마술의 내용은 다음과 같다.

• 1단계: 밥이 방에 들어가 바깥과 완전히 단절된다. 밥은 캐서린과만 소통할 수 있다. 그다음 앨리스가 캐서린에게 2 이상 $5\, 000$ 이하의 수 $n$을 알려준다.
• 2단계: 캐서린이 앨리스에게 1 이상 $10^{18}$ 이하의 수 $X$를 알려준다.
• 3단계: 앨리스가 정확히 $n$개의 정점을 가진 트리를 만들어 캐서린에게 준다.
• 4단계: 캐서린이 트리에서 최대 $\left\lfloor \frac{n-2}{2} \right\rfloor$개의 간선을 제거하고, 남은 간선을 밥에게 준다.
• 5단계: 밥이 그래프를 자세히 관찰하고 캐서린이 앨리스에게 알려준 수를 말한다.

하지만 앨리스와 밥은 자신들이 이 마술을 성공할 만큼 똑똑하지 않다고 여겨 도움을 청했다. 앨리스의 전략과 밥의 전략을 구현하는 프로그램을 작성하라.

$1 ≤ X ≤ 10^{18}$.