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)~.