늑대인간

이바라키현에는 $N$개의 도시와 $M$개의 도로가 있다. 도시는 인구가 적은 순서대로 0부터 $N-1$까지 번호가 붙어 있다. 각 도로는 서로 다른 두 도시를 잇고, 양방향으로 지날 수 있다. 어떤 도시에서든 도로를 따라 다른 모든 도시로 갈 수 있다.

$Q$번의 여행을 계획했다. 여행 $i$ ($0 ≤ i ≤ Q-1$)는 도시 $S_i$에서 도시 $E_i$까지 가는 여행이다.

당신은 늑대인간이다. 인간 형태와 늑대 형태가 있다. 여행을 시작할 때는 인간 형태이고, 여행이 끝날 때는 늑대 형태여야 한다. 여행 중에 정확히 한 번 변신해야 한다(인간 형태에서 늑대 형태로 바뀌는 것). 변신은 도시에 있을 때만 할 수 있으며, 그 도시는 $S_i$나 $E_i$일 수도 있다.

인간 형태일 때는 인구가 적은 도시를 피해야 하고, 늑대 형태일 때는 인구가 많은 도시를 피해야 한다. 각 여행 $i$마다 피해야 할 도시를 정하는 두 기준 $L_i$와 $R_i$ ($0 ≤ L_i ≤ R_i ≤ N-1$)가 있다. 인간 형태에서는 도시 $0, 1, ..., L_i-1$을 피한다. 늑대 형태에서는 도시 $R_i+1, R_i+2, ..., N-1$을 피한다. 따라서 여행 $i$에서는 도시 $L_i, L_i+1, ..., R_i$ 중 한 곳에서만 변신할 수 있다.

각 여행에 대해 이 조건을 모두 지키며 $S_i$에서 $E_i$까지 갈 수 있는지 판단한다. 경로의 길이는 제한이 없다.

2 ≤ $N$ ≤ 200,000. $N-1$ ≤ $M$ ≤ 400,000. 1 ≤ $Q$ ≤ 200,000. 각 $j$ ($0 ≤ j ≤ M-1$)에 대해 0 ≤ $X_j$ ≤ $N-1$, 0 ≤ $Y_j$ ≤ $N-1$, $X_j ≠ Y_j$이다. 어떤 도시에서든 도로를 이용해 다른 모든 도시로 갈 수 있다. 같은 두 도시를 잇는 도로는 최대 하나뿐이다. 각 $i$ ($0 ≤ i ≤ Q-1$)에 대해 0 ≤ $L_i$ ≤ $S_i$ ≤ $N-1$, 0 ≤ $E_i$ ≤ $R_i$ ≤ $N-1$, $S_i ≠ E_i$, $L_i ≤ R_i$이다.