완전 이진 트리

k-레벨 완전 이진 트리는 모든 내부 노드의 자식이 2개이고 모든 단말 노드가 레벨 k에 있는 이진 트리이다. 레벨 1에는 2^0개, 레벨 2에는 2^1개, ..., 레벨 k에는 2^(k-1)개의 노드가 있으며 전체 노드 수는 2^k - 1이다.

두 개의 k-레벨 완전 이진 트리 T1, T2가 있다. 각 트리의 단말 노드에는 집합 L = {1, 2, ..., N}의 서로 다른 정수가 하나씩 적혀 있고, 여기서 N = 2^(k-1)이다.

L의 부분집합 S가 다음 조건을 만족해야 한다.

• S에 속한 임의의 두 정수 x, y에 대해, T1에서 x와 y가 적힌 단말 노드 사이의 거리와 T2에서 x와 y가 적힌 단말 노드 사이의 거리가 같아야 한다. 두 노드 사이의 거리는 두 노드를 잇는 경로에 포함된 간선 수이다.
• 이러한 조건을 만족하는 집합 중 S의 크기는 최대여야 한다.

예를 들어 k = 4이고 두 트리의 단말 노드에 적힌 수를 왼쪽부터 차례로 읽은 결과가 각각 (4, 2, 1, 3, 6, 7, 5, 8)과 (2, 7, 4, 8, 3, 1, 6, 5)라면 가능한 최대 집합의 하나는 {1, 3, 7, 8}이다. 이 집합에서는 어떤 두 원소를 골라도 두 트리에서의 단말 노드 사이 거리가 서로 같다.

첫 줄에 두 트리의 레벨 k가 주어진다. (1 <= k <= 12)

둘째 줄에는 T1의 단말 노드에 적힌 N = 2^(k-1)개의 정수가 왼쪽에서 오른쪽 순서로 주어진다.

셋째 줄에는 T2의 단말 노드에 적힌 N개의 정수가 왼쪽에서 오른쪽 순서로 주어진다.

각 줄의 정수들은 1부터 N까지의 순열이다.

조건을 만족하는 최대 집합 S의 크기를 출력한다.