Speedrun

Marcel started speedrunning in hopes of setting a new World Record (WR). Sadly, he cannot master the newly discovered strats, so he has to find a way to gain an unfair advantage.

The game he is trying to get good at is called Tree Souls III, and he is going for a WR in the full-tree% category.

As the name implies, the game takes place on a tree: a graph with $N$ vertices numbered from $1$ to $N$ and $N - 1$ edges, with no cycles.

The game works as follows. The character is placed on an arbitrary node in the tree. He can choose an integer $x$ and try to walk from his current node to node $x$. If there is an edge between $x$ and his current node, he moves to $x$. Otherwise nothing happens. A speedrun is valid if he visits each node at least once.

Here comes the cheating part. He does not know the edge-teleportation glitch, so he sets the seed for his world himself. That means he knows the shape of the tree before the run starts. Memorizing the tree would be too obvious, and he would be instantly banned from the speedrunning community. So he tampers with the code and puts hints in each node instead. A hint is a binary string of length $l$, and $l$ is the same for every hint in every node. When he stands on a node, he can read the hint assigned to that node.

• $1 ≤ N ≤ 1\,000$
• Let $Q$ be the number of calls to goTo that returned false. The constraints on $l$ and $Q$ that must be respected to earn score for each subtask are outlined below.