Finding the Special Node

This is an interactive problem. Given a rooted binary tree with \(N\) nodes (the root is node 1), there is exactly one unknown special node in the tree. Your task is to determine the identity of this special node.

You are provided with a parent's array \(p\) of length \(N-1\) where the \(i\)th element satisfies \(1 \le p_i \le i+1\) and describes the parent of node \(i+2\). All elements in \(p\) are distinct.

You can ask at most 35 queries using the function ask(int x). Each query checks if the subtree rooted at node \(x\) contains the special node. The function returns \(1\) if the special node is in the subtree of \(x\) (including \(x\) itself) and \(0\) otherwise.

You need to implement the function int solve(int N, std::vector<int> p) which will be called exactly once. This function should return the id of the special node.

Note: For simulation and testing purposes, the input will include an extra integer representing the special node. In an actual interactive scenario this would not be given, but you are allowed to use this value to simulate the interactive responses via the ask function.

The formulas used are in \(\LaTeX\): for example, the parent's array constraints are given by \(1 \le p_i \le i+1\) and the tree contains \(N\) nodes.

inputFormat

The first line contains an integer \(N\), the number of nodes in the tree. The second line contains \(N-1\) space-separated integers representing the parent's array \(p\). The third line contains an integer denoting the special node (this is provided for simulation purposes).

outputFormat

Output the id of the special node.

sample

3
1 1
2

2