1646번 - 피이보나치 트리

0번째와 1번째 피이보나치 트리는 단일 노드로 이루어져 있다. 1보다 큰 모든 i번째 피이보나치 트리는 다음과 같은 방법을 통해 만들 수 있다.

1. 새로운 노드 r을 만든다. 이 노드는 i번째 피이보나치 트리의 루트가 된다.
2. (i-1)번째와 (i-2)번째 피이보나치 트리를 만든다.
3. (i-2)번째 피이보나치 트리를 노드 r의 왼쪽 부분 트리로 만든다.
4. (i-1)번째 피이보나치 트리를 노드 r의 오른쪽 부분 트리로 만든다.

피이보나치 트리의 정점의 개수는 정말 빠르게 증가한다. 예를 들어, 50번째 피이보나치 트리는 약 4×10¹⁰개의 정점을 가지고 있다.

피이보나치 트리의 정점에 번호를 매기는 순서는 트리를 전위순회할 때 방문하는 순서대로 번호를 매긴다.

예를 들어, 3번째 피이보나치 트리는 다음과 같다.

N과 시작 위치와 도착 위치가 들어오면, N번째 피이보나치 트리에서 시작 위치에서 도착 위치로 가는 최단 경로를 구하는 프로그램을 작성하시오. 각 노드사이의 거리는 1이다.

첫째 줄에 N과 시작 위치와 도착 위치가 공백을 사이에 두고 주어진다. N은 50보다 작거나 같은 자연수 또는 0이다. 시작 위치와 도착 위치는 1,000,000,000보다 작거나 같으며, N번째 피이보나치 트리의 정점의 수보다 작거나 같은 자연수이다. 시작 위치와 도착 위치는 서로 다른 수이다.

첫째 줄에 시작 위치부터 도착 위치로 가는 최단 경로를 찾는다. L은 왼쪽 자식으로 이동하는 것이고, R은 오른쪽 자식으로 이동하는 것이고, U는 부모로 이동하는 것이다.