Consecutive Ordering

An interval graph is the intersection graph of a family $F = \{I_1, I_2, \ldots, I_n\}$ of closed intervals on the real line. Two vertices $v_i$ and $v_j$ are joined by an edge exactly when the corresponding intervals $I_i$ and $I_j$ intersect. The family $F$ is called an interval representation of the graph. A unit interval graph is an interval graph for which some interval representation has all intervals of the same length. Figure 1 shows a unit interval graph together with an interval representation of it.

(a) A unit interval graph $G$.

(b) An interval representation of the graph $G$.

Figure 1. A unit interval graph and its interval representation.

The closed neighbourhood $N[v_i]$ of a vertex $v_i$ of a graph $G$ is the set of vertices adjacent to $v_i$ together with $v_i$ itself, that is, $N[v_i] = \{v_i\} \cup \{v_j : v_j v_i \in E(G)\}$. For the graph $G$ of Figure 1(a), $N[v_1] = \{v_1, v_2, v_3\}$ and $N[v_5] = \{v_2, v_3, v_4, v_5, v_6\}$.

Write $\rho(v_i)$ for the position of $v_i$ in an ordering of the vertices. Under the ordering $(v_1, v_2, \ldots, v_{17})$ of the vertices of $G$, in which $\rho(v_i) = i$ for every $v_i$, the closed neighbourhood $N[v_i]$ of every vertex is consecutive: the positions of the vertices in $N[v_i]$ are integers that follow one after another, without gaps, from the smallest to the largest. An ordering of the vertices of a graph is consecutive if the closed neighbourhood of every vertex of the graph is consecutive. For the graph $G$ of Figure 1(a), the ordering $(v_1, v_2, \ldots, v_{15}, v_{17}, v_{16})$ with $v_{16}$ and $v_{17}$ exchanged, where $\rho(v_{17}) = 16$, $\rho(v_{16}) = 17$, and $\rho(v_i) = i$ for every other vertex, is consecutive as well. The ordering $(v_2, v_1, v_3, v_4, \ldots, v_{17})$ is not consecutive, because the closed neighbourhood of $v_5$ is not consecutive.

You are given $n$ closed intervals of the same length, $I_1, I_2, \ldots, I_n$, listed in non-decreasing order of their left endpoints, and an ordering $(v_{i_1}, v_{i_2}, \ldots, v_{i_n})$ of the vertices of the unit interval graph defined on those $n$ intervals. Write a program that decides whether the ordering is consecutive.

Your program reads from standard input. The input consists of $T$ test cases, and $T$ is given on the first line.

Each test case begins with a line containing two positive integers $n$ and $l$, the number of intervals and their common length, where $n$ is at most 100,000 and $l$ is at most 100,000,000. The next $n$ lines contain the left endpoints of $I_1, I_2, \ldots, I_n$, one per line, and the left endpoint of $I_i$ is less than or equal to the left endpoint of $I_j$ whenever $i < j$. Every endpoint, left or right, lies between -100,000,000 and 100,000,000, inclusive. The following $n$ lines contain an ordering of the vertices of the unit interval graph defined on those intervals, one vertex number per line, from the first position to the last.

Your program writes to standard output. For each test case, print exactly one line containing an integer that tells whether the given ordering is consecutive. Print 1 if it is, and -1 otherwise.