Complete Binary Tree

A k-level complete binary tree is a binary tree in which every internal node has exactly two children and every leaf is on level k. Level 1 has 2^0 nodes, level 2 has 2^1 nodes, ..., level k has 2^(k-1) nodes, so the tree has 2^k - 1 nodes in total.

There are two k-level complete binary trees, T1 and T2. Each leaf of each tree is labeled with a distinct integer from the set L = {1, 2, ..., N}, where N = 2^(k-1).

Find a subset S of L satisfying the following conditions.

• For every pair of integers x and y in S, the distance between the leaves labeled x and y in T1 must be equal to the distance between the leaves labeled x and y in T2. The distance between two nodes is the number of edges on the path connecting them.
• Among all subsets satisfying this condition, S must have maximum size.

For instance, when k = 4 and the leaf labels of the two trees, read from left to right, are (4, 2, 1, 3, 6, 7, 5, 8) and (2, 7, 4, 8, 3, 1, 6, 5), one maximum valid subset is {1, 3, 7, 8}. For any two elements chosen from this subset, the distance between their leaves is the same in both trees.

The first line contains the level k of the two trees. (1 <= k <= 12)

The second line contains the N = 2^(k-1) integers written on the leaves of T1, from left to right.

The third line contains the N integers written on the leaves of T2, from left to right.

Each of the two lines is a permutation of the integers from 1 to N.

Print the size of the largest subset S satisfying the condition.