Werewolf timer 4초 memory 512MB

일본 이바라키 현에는 N개의 도시와 M개의 도로가 있다.

도시들은 인구의 수가 작은 도시부터 큰 도시의 순서로 0부터 N-1까지의 번호로 표현된다.

각각의 도로는 한 쌍의 서로 다른 도시를 연결하며, 양방향으로 이동할 수 있다.

어떤 두 도시를 고르더라도 한 도시에서 다른 도시로 한 개 이상의 도로를 따라서 이동할 수 있다.

당신은 Q번 여행을 하려고 하는데, 각 여행은 0부터 Q-1까지 숫자로 표현된다.

여행 i(0 ≤ i ≤ Q-1)는 도시 S_i에서 출발해서 도시 E_i에 도착하는 것이다.

당신은 늑대인간이다.

늑대인간에는 두 형태가 있는데, 인간 형태와 늑대 형태이다.

매 여행마다, 당신은 인간 형태로 여행을 시작한다.

여행이 끝났을 때 당신은 반드시 늑대 형태여야 한다.

여행 도중에, 변신(인간 형태에서 늑대 형태로 바뀌는 것)을 정확하게 한번만 해야 한다.

변신은 도시에 있을 때에만 할 수 있다 (S_i 또는 E_i에서도 변신할 수 있다).

늑대인간으로 사는 것은 쉽지 않다.

인간 형태일 때는 사람이 적은 도시를 피해야 하고 늑대 형태일 때는 사람이 많은 도시를 피해야 한다.

각 여행 i마다 두 경계값 Li와 Ri가 있는데, 어느 도시들을 방문하면 안되는지를 알려준다.

구체적으로는, 당신은 여행 i에서 인간 형태일 때는 도시 0, 1, ..., L_i - 1을 방문하면 안되고, 늑대 형태일 때는 도시 R_i + 1, R_i + 2, ... , N - 1을 방문하면 안된다.

이는 당신은 도시 L_i, L_i + 1, ... , R_i 중 하나에서만 변신할 수 있다는 뜻이다.

당신이 할 일은 각각의 여행마다 위에서 주어진 조건을 모두 만족하면서 도시 S_i에서 출발해서 도시 E_i에 도착하는 것이 가능한지 판단하는 것이다.

만약 도착할 수 있다면 이 경로의 길이는 어떤 값이어도 상관없다.​