11063번 - Consecutive Ordering 다국어

An interval graph is the intersection graph of family F = {I₁, I₂, ..., I_n} of closed intervals on the real line, where two vertices, v_i and v_j, are connected with an edge if and only if their corresponding intervals, I_i and I_j, intersect. The family F is usually called an interval representation for the graph. A unit interval graph is an interval graph with an interval representation in which all the intervals have the same length. Refer to Figure 1 for an example of a unit interval graph and its interval representation.

(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 refers to the set of vertices adjacent to v_i along with v_i itself, i.e., N[v_i] = {v_i} ∪ {v_j : (v_j, v_i) is an edge of G}. For the graph G shown in Figure 1(a), we have N[v₁] = {v₁, v₂, v₃} and N[v₅] = {v₂, v₃, v₄, v₅, v₆}. Under the ordering (v₁, v₂, ..., v₁₇) of the vertices of G in which the position of v_i, denoted by ρ(v_i), is i for all v_i, the closed neighbourhood N[v_i] of every vertex v_i is consecutive, i.e., the positions of vertices in N[v_i] are integers which follow one after another, without gaps, from smallest to largest. An ordering of the vertices of a graph is said to be consecutive if the closed neighborhood of every vertex of the graph is consecutive. For the graph G of Figure 1(a), the ordering (v₁, v₂, ..., v₁₅, v₁₇, v₁₆) with v₁₆ and v₁₇ being switched, where ρ(v₁₇) = 16, ρ(v₁₆) = 17, and ρ(v_i) = i for all v_i ≠ v₁₆, v₁₇, is also consecutive. However, (v₂, v₁, v₃, v₄, ..., v₁₇) is not a consecutive ordering because the closed neighbourhood of v₅ is not consecutive.

Given n closed intervals of the same length, I₁, I₂, ..., I_n, in a non-decreasing order of their left endpoints and an ordering (v_i1, v_i2, ..., v_in) of the vertices of the unit interval graph defined on the n intervals, write a program to test whether the ordering is consecutive or not.

Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case begins with a line containing two positive integers n and l, where n ≤ 100,000 and l ≤ 100,000,000, respectively representing the number and the length of intervals. It follows n lines containing, one by one, the left endpoints of intervals, I₁, I₂, ..., I_n, in which the left endpoint of I_i is always less than or equal to that of I_j if i < j. You may assume that the endpoints, left or right, of intervals are between -100,000,000 and 100,000,000, inclusive. It follows n lines again, containing an ordering of the vertices of the unit interval graph defined on the n intervals, one vertex per line.

Your program is to write to standard output. For each test case, print exactly one line that contains an integer indicating whether the given ordering is consecutive. If yes, the integer must be 1; otherwise -1.