We need to simplify the input. Let's define a graph on $$$2n$$$ vertices $$$V_1, V_2, ..., V_n, W_1, W_2, ..., W_n$$$. $$$V_i$$$ and $$$W_i$$$ represent the state of being in vertex $$$i$$$, but $$$W_i$$$ imposes the additional restriction that you just came from the largest edge.

For a vertex $$$i$$$ let $$$ij$$$ be the largest edge connected with $$$i$$$, and let $$$ik$$$ to be the second largest, or $$$j$$$ if it's the only neighbor. We will add the following edges:

• $$$V_i \rightarrow V_j$$$ or $$$W_j$$$ depending on whether $$$ij$$$ is the biggest edge for $$$j$$$ or not.

• $$$W_i \rightarrow V_k$$$ or $$$W_k$$$ depending on whether $$$ik$$$ is the biggest edge for $$$k$$$ or not.

The task now simply to count the number of vertices among $$$V_1, V_2, ..., V_n$$$ that end up at $$$V_p$$$ or $$$W_p$$$ after taking $$$k$$$ steps in this state graph. Now we have a bruteforce $$$\operatorname{O}(nk)$$$ solution per query. You can also achieve this complexity by simple brute force.

It's possible to solve this task in $$$\operatorname{O}(n \log k)$$$ per query by going through each vertex and finding where it ends up in $$$k$$$ steps using binary lifting. This gets the first 2 subtasks and 69 points.

Full points may or may not be easier than getting just 69.

We need to understand the structure of the graph we have built. Each component looks a bunch of rooted trees, where some of the roots have been connected in a cycle. This means that if $$$t$$$ is in a cycle of length $$$3$$$, and min number of steps for some vertex $$$s$$$ to reach $$$t$$$ is $$$4$$$ for example, then it will visit $$$t$$$ after $$$7, 10, 13, ..., 67, ...$$$ steps as well.

Let's focus on $$$V_p$$$ for now, as all these checks can be done for $$$W_p$$$ just as well. We will reverse all the edges and calculate the distance from $$$V_p$$$ to all other vertices. Let these distances be called $$$d_i$$$. Also let $$$c$$$ be the length of the cycle $$$V_p$$$ is in or $$$93858158317519$$$ if it's not in a cycle. Then all we have to do to check if $$$V_i$$$ reaches $$$V_p$$$ in $$$k$$$ steps is:

• $$$d_{V_i} \ge k$$$
• $$$d_{V_i} - k$$$ is a multiple of $$$c$$$

So we can answer a query in $$$\operatorname{O}(n)$$$ per query.

Look at the manhattan distance is hard and annoying. A better and more straightforward calculation would be to find the number