Werewolf

There are $N$ cities and $M$ roads in Ibaraki Prefecture, Japan. Cities are numbered from 0 through $N-1$ in increasing order of their population. Each road connects a pair of distinct cities and can be traveled in both directions. You can travel from any city to any other city by using one or more of these roads.

You have planned $Q$ trips, numbered from 0 through $Q-1$. Trip $i$ ($0 ≤ i ≤ Q-1$) travels from city $S_i$ to city $E_i$.

You are a werewolf. You have two forms: human form and wolf form. At the beginning of each trip you are in human form. At the end of each trip you must be in wolf form. During a trip you have to transform (change from human form to wolf form) exactly once. You can transform only when you are in a city, and that city may be $S_i$ or $E_i$.

You must avoid low-populated cities when you are in human form, and avoid highly-populated cities when you are in wolf form. For each trip $i$, two thresholds $L_i$ and $R_i$ ($0 ≤ L_i ≤ R_i ≤ N-1$) decide which cities to avoid. In human form you must avoid cities $0, 1, ..., L_i-1$. In wolf form you must avoid cities $R_i+1, R_i+2, ..., N-1$. So in trip $i$, you can transform only in one of the cities $L_i, L_i+1, ..., R_i$.

For each trip, determine whether it is possible to travel from $S_i$ to $E_i$ while satisfying these constraints. The route can have any length.

2 ≤ $N$ ≤ 200,000. $N-1$ ≤ $M$ ≤ 400,000. 1 ≤ $Q$ ≤ 200,000. For each $j$ ($0 ≤ j ≤ M-1$): 0 ≤ $X_j$ ≤ $N-1$, 0 ≤ $Y_j$ ≤ $N-1$, and $X_j ≠ Y_j$. Any city can reach any other city by using roads. Each pair of cities is directly connected by at most one road. For each $i$ ($0 ≤ i ≤ Q-1$): 0 ≤ $L_i$ ≤ $S_i$ ≤ $N-1$, 0 ≤ $E_i$ ≤ $R_i$ ≤ $N-1$, $S_i ≠ E_i$, and $L_i ≤ R_i$.