인피니트리

이 문제는 정이진 트리의 두 노드 사이의 거리를 구하는 문제이다. 이런, 너무 쉬운가?! 좋다, 이제 트리는 무한할 수도 있다. 이대로 계속하다가는 알레프 수까지 올라가기 시작할 것이다.

이 문제에서 트리는 하나의 노드 $X$이거나, 왼쪽 부분 트리와 오른쪽 부분 트리라는 두 트리가 연결된 노드 $X$이다. 두 경우 모두 $X$이 트리의 루트이다. 트리가 하나의 노드로만 이루어지지 않았다면, 왼쪽과 오른쪽 부분 트리 각각의 루트가 $X$의 유일한 두 자식이다.

$0$부터 $\mathbf{N}$까지의 번호가 붙은 색의 집합이 있다. 각 노드는 정확히 하나의 색을 가진다. 각 색의 노드는 없거나, 하나이거나, 여러 개일 수 있다. 색이 $0$인 각 노드(흰색)는 리프 노드이다(즉, 자식이 없다). $1 \le i \le \mathbf{N}$인 각 $i$색 노드는 정확히 $2$개의 자식을 가진다. 왼쪽 자식의 색은 $\mathbf{L_i}$이고 오른쪽 자식의 색은 $\mathbf{R_i}$이다. 트리의 루트는 $1$색(검은색)이다. 트리의 노드 수는 유한할 수도 있고 가산 무한일 수도 있음에 유의하라.

예를 들어, 다음 그림은 목록 $\mathbf{L} = [3, 0, 0]$와 $\mathbf{R} = [2, 0, 2]$로 정의되는 유한 트리를 보여 준다. 색 $2$은 파란색이고 색 $3$은 노란색이다.

트리에서 두 노드 사이의 거리는 한 노드에서 다른 노드로 이동하는 데 필요한 최소 이동 횟수이다. 한 번의 이동은 한 노드에서 그 노드의 직계 부모 또는 직계 자식으로 이동하는 것이다.

트리의 노드에는 양의 정수를 사용해 인덱스를 붙인다. 루트의 인덱스는 $1$이다. 그다음 다른 노드에는 연속된 정수로 인덱스를 붙이며, 루트까지의 거리가 더 작은 노드에 먼저 인덱스를 붙인다. 루트까지의 거리가 같은 노드들 사이에서는 더 왼쪽에 있는 노드에 먼저 인덱스를 붙인다. 예를 들어, 다음 그림은 앞서 제시한 트리의 각 노드에 인덱스를 추가한 것이다. 각 노드의 인덱스는 그 색과 무관하다는 점에 유의하라.

또 다른 예로, 다음 그림은 목록 $\mathbf{L} = [3, 4, 2, 4]$와 $\mathbf{R} = [2, 2, 4, 0]$으로 정의되는 무한 트리의 첫 $33$개 노드를 보여 준다. 색 $4$은 초록색이다.

트리를 정의하는 목록 $\mathbf{L}$와 $\mathbf{R}$, 그리고 트리에서 서로 다른 두 노드의 인덱스가 주어질 때, 그 두 노드 사이의 거리를 반환하라.

제한

시간 제한: 90초. 메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. $1 \le \mathbf{N} \le 50$. $0 \le \mathbf{L_i} \le \mathbf{N}$. $0 \le \mathbf{R_i} \le \mathbf{N}$. $\mathbf{A} \lt \mathbf{B} \le 10^{18}$. $\mathbf{L}$와 $\mathbf{R}$로 정의되는 트리는 적어도 $\mathbf{B}$개의 노드를 가진다.

테스트 세트 1 (Visible Verdict)

$\mathbf{A} = 1$.

테스트 세트 2 (Hidden Verdict)

$1 \le \mathbf{A} \le 10^{18}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 세 줄로 이루어진다. 첫 번째 줄에는 각각 트리를 정의하는 목록의 크기와 거리를 계산해야 하는 두 노드의 인덱스인 $\mathbf{N}$, $\mathbf{A}$, $\mathbf{B}$가 주어진다. 두 번째 줄에는 위에서 설명한 $\mathbf{N}$개의 정수 $\mathbf{L_1}, \mathbf{L_2}, \dots, \mathbf{L_N}$가 주어지고, 세 번째 줄에는 $\mathbf{N}$개의 정수 $\mathbf{R_1}, \mathbf{R_2}, \dots, \mathbf{R_N}$가 주어진다.

각 테스트 케이스마다 Case #$x$: $y$을 포함하는 한 줄을 출력한다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 목록 $\mathbf{L}$와 $\mathbf{R}$으로 정의되는 트리에서 인덱스가 $\mathbf{A}$과 $\mathbf{B}$인 노드 사이의 거리이다.

예제 케이스 #1과 #2의 트리는 문제 설명에 처음으로 나온 트리이다. 예제 케이스 #3와 #4의 트리는 문제 설명에 마지막으로 나온 트리이다. 아래의 추가 예제에도 동일하게 적용된다. 예제 케이스 #5에서는 일부 색이 트리에 존재하지 않을 수도 있다는 점에 유의하라.

추가 예제 - 테스트 세트 2