Count

This is an interactive problem.

A quintuple $(T, I, S_V, S_E, \iota)$ is given, where:

• $T$ is a rooted tree with $n$ vertices, $T = (V, E)$, where $V$ is the vertex set and $E$ is the edge set. The vertices are numbered $1, 2, \ldots, n$, and the root is vertex 1.
• $I$ is a set whose elements are called information. There are two special elements: the unit element $\epsilon$ and the illegal element $\perp$. General information has two attributes, a vertex set and an edge set. The unit element has only an edge set attribute. The illegal element has neither.
• For general information $o \in I \setminus \{\epsilon, \perp\}$, the vertex set $S_V(o)$ is a subset of $V$ with $|S_V(o)| = 2$.
• For $o \in I \setminus \{\perp\}$, the edge set $S_E(o)$ is a subset of $E$. The edge set of the unit element is empty: $S_E(\epsilon) = \emptyset$.
• For every edge $e = (u, v) \in E$, there is information $\iota(e) \in I$ with $S_V(\iota(e)) = \{u, v\}$ and $S_E(\iota(e)) = \{e\}$.

Information is combined by two operations, $R$ and $C$. For all $a, b \in I$, let $r = R(a, b)$ and $c = C(a, b)$, where $r, c \in I$.

1. If $a = \epsilon$, then $r = c = b$. If $b = \epsilon$, then $r = c = a$.
2. If $a = \perp$ or $b = \perp$, then $r = c = \perp$.
3. Otherwise, if $S_E(a) \cap S_E(b) \neq \emptyset$ or $|S_V(a) \cap S_V(b)| \neq 1$, then $r = c = \perp$.
4. Otherwise, $S_E(r) = S_E(c) = S_E(a) \cup S_E(b)$, $S_V(r) = S_V(a)$, and $S_V(c) = S_V(a) \oplus S_V(b)$, where $A \oplus B = (A \cup B) \setminus (A \cap B)$.

The distance between two vertices of $T$ is the number of edges on the unique simple path joining them.

You are given $q$ queries. Each query has a vertex $u$ and a non-negative integer $d$. Let $X$ be the set of vertices whose distance to $u$ is at most $d$, and let $Y = \{(a, b) \in E \mid a, b \in X\}$ be the set of edges with both endpoints in $X$.

It can be shown that, starting from $\epsilon$ and all $\iota(e)$ ($e \in E$), a finite number of calls to $R$ and $C$ produces information $o$ with $o \neq \perp$ and $S_E(o) = Y$. If $d = 0$, the output must be the unit element $\epsilon$.

For each query, construct such an information $o$, using at most $M$ calls to $R$ and $C$ in total.

For all test cases, $1 \leq n \leq 2 \times 10^5$ and $1 \leq q \leq 10^6$. For each query, $1 \leq u \leq n$ and $1 \leq d \leq n-1$.

• Property A: For all $i = 1, 2, \ldots, n-1$, the parent of $i+1$ is $i$.
• Property B: For all queries, $u = 1$.
• Property C: For all queries, $d \leq 100$.
• Property D: For all queries, $d \geq 1000$.