Subtask 1

You choose a vertex $V$ where you transform yourself from human form to wolf form.

For each choice of $V$, you need to decide whether it is possible to travel from $S_i$ to $V$ in human form (i.e. only using vertices whose indices are $\ge L_i$), and to decide whether it is possible to travel from $V$ to $E_i$ in wolf form (i.e. only using vertices whose indices are $\le R_i$).

The time complexity of this solution is $\mathcal{O}(QN(N+M))$.

Subtask 2

Determine the set of vertices you can visit from $S_i$ in human form, and determine the set of vertices you can visit from $E_i$ in wolf form.

Then check whether these two sets intersect.

The time complexity of this solution is $\mathcal{O}(Q(N+M))$.

Subtask 3

Let $U_i$ be the set of the vertices which are reachable from $S_i$ by passing only vertices with index at least $L_i$. Similarly, let $V_i$ be the set of the vertices which are reachable from $E_i$ by passing only vertices with index at most $R_i$. Note that $U_i$ forms a range on the line on which cities are located. This range can be efficiently computed using doubling or Segment tree. $V_i$ can be similarly computed. Then, we can answer the query by checking whether these two ranges intersect.

Subtask 4

We can construct a rooted tree so that $U_i$ forms a subtree. This can be done using adding vertices to a disjoint set union structure in the descending order of indices. Then, using Euler-Tour on this tree, we can obtain a sequence of vertices and every $U_i$ corresponds to a contiguous segment of this sequence. We can compute a similar sequence for $V_i$. Then, we can answer the query by checking whether two segments for $U_i$ and $V_i$ share a vertex. This can be done by the sweep line algorithm with a segment tree. The time complexity of this solution is $\mathcal{O}((Q+M)\log N)$.