연속 순서

구간 그래프는 실직선 위의 닫힌 구간 모임 $F = \{I_1, I_2, \ldots, I_n\}$의 교차 그래프다. 두 정점 $v_i$와 $v_j$는 대응하는 구간 $I_i$와 $I_j$가 만날 때에만 간선으로 이어진다. 이때 $F$를 그 그래프의 구간 표현이라고 한다. 단위 구간 그래프는 모든 구간의 길이가 같은 구간 표현이 존재하는 구간 그래프다. 그림 1은 단위 구간 그래프와 그 구간 표현의 예다.

(a) 단위 구간 그래프 $G$.

(b) 그래프 $G$의 구간 표현.

그림 1. 단위 구간 그래프와 그 구간 표현.

그래프 $G$의 정점 $v_i$의 닫힌 이웃 $N[v_i]$는 $v_i$에 인접한 정점 전체에 $v_i$ 자신을 더한 집합이다. 즉 $N[v_i] = \{v_i\} \cup \{v_j : v_j v_i \in E(G)\}$이다. 그림 1(a)의 그래프 $G$에서는 $N[v_1] = \{v_1, v_2, v_3\}$이고 $N[v_5] = \{v_2, v_3, v_4, v_5, v_6\}$이다.

정점 순서에서 $v_i$가 놓인 위치를 $\rho(v_i)$로 쓴다. 모든 $v_i$에 대해 $\rho(v_i) = i$인 순서 $(v_1, v_2, \ldots, v_{17})$에서는 모든 정점의 닫힌 이웃 $N[v_i]$가 연속이다. 즉 $N[v_i]$에 속한 정점의 위치가 가장 작은 값부터 가장 큰 값까지 빈틈 없이 하나씩 이어지는 정수다. 그래프의 모든 정점의 닫힌 이웃이 연속이면 그 정점 순서를 연속 순서라고 한다. 그림 1(a)의 그래프 $G$에서 $v_{16}$과 $v_{17}$을 맞바꾼 순서 $(v_1, v_2, \ldots, v_{15}, v_{17}, v_{16})$도 연속 순서다. 이 순서에서는 $\rho(v_{17}) = 16$, $\rho(v_{16}) = 17$이고 나머지 정점은 $\rho(v_i) = i$이다. 반면 $(v_2, v_1, v_3, v_4, \ldots, v_{17})$은 $v_5$의 닫힌 이웃이 연속이 아니므로 연속 순서가 아니다.

길이가 같은 닫힌 구간 $I_1, I_2, \ldots, I_n$이 왼쪽 끝점의 비내림차순으로 주어지고, 이 $n$개의 구간으로 정의되는 단위 구간 그래프의 정점 순서 $(v_{i_1}, v_{i_2}, \ldots, v_{i_n})$이 주어진다. 이 순서가 연속 순서인지 판정하는 프로그램을 작성하시오.

프로그램은 표준 입력에서 읽는다. 입력은 $T$개의 테스트 케이스로 이루어지고, 첫째 줄에 $T$가 주어진다.

각 테스트 케이스의 첫째 줄에는 구간의 개수 $n$과 구간의 공통 길이 $l$이 주어진다. 둘 다 양의 정수이고, $n$은 100,000 이하, $l$은 100,000,000 이하다. 이어지는 $n$개의 줄에는 구간 $I_1, I_2, \ldots, I_n$의 왼쪽 끝점이 한 줄에 하나씩 주어진다. $i < j$이면 $I_i$의 왼쪽 끝점은 $I_j$의 왼쪽 끝점보다 작거나 같다. 왼쪽이든 오른쪽이든 모든 끝점은 -100,000,000 이상 100,000,000 이하다. 그 다음 $n$개의 줄에는 이 구간들로 정의되는 단위 구간 그래프의 정점 순서가 첫 번째 위치부터 마지막 위치까지 한 줄에 하나씩 주어진다.

프로그램은 표준 출력에 쓴다. 각 테스트 케이스마다 주어진 순서가 연속 순서인지를 나타내는 정수 하나를 한 줄에 출력한다. 연속 순서이면 1을, 아니면 -1을 출력한다.