P14279 [ROI 2014 Day2] 乌拉尔高速公路

**译自 [ROI 2014](https://neerc.ifmo.ru/school/archive/2013-2014.html) Day2 T4.** ***[Магистраль «Урал»](https://neerc.ifmo.ru/school/archive/2013-2014/ru-olymp-roi-2014-statement-day2.pdf)***

计划修建一条名为“乌拉尔”的新高速公路。高速公路的耐久性取决于其下方所分布的岩层结构。一个岩层是由同一种岩石组成的地质体。 在未来的高速公路下方共有 $n$ 层水平岩层。地质勘探确定了每一层岩层在高速公路下方的起点与终点位置。然而，这些岩层在深度方向上的顺序尚无法确定。 在高速公路沿线的若干位置进行了垂直钻探。每口钻井穿过了钻井位置下方的若干上部岩层。对于每口钻井，已知钻井从地表向下依次穿过的岩层顺序。如果某层岩石没有出现在该钻井中，说明它位于钻井的底部以下。 :::align{center}  ::: 你的任务是编写一个程序，根据钻探数据，确定一种可能的岩层深度顺序，使其不与已知的地质信息相矛盾。

第一行包含一个整数 $n$ —— 岩层的数量。岩层编号为 $1$ 到 $n$，顺序任意。 接下来的 $n$ 行中，第 $i$ 行包含两个整数 $l_i$ 和 $r_i$（$0 \leqslant l_i < r_i \leqslant 10^9$），表示第 $i$ 层岩石在高速公路下方的起点与终点距离。 接下来一行包含一个整数 $m$ —— 钻井的数量。 随后 $m$ 行描述每口钻井的勘探结果。每行格式如下： $x\ k\ s_1\ s_2\ \ldots\ s_k$ 其中： - $x$ —— 钻井的位置（距公路起点的距离，$0 \leqslant x \leqslant 10^9$）； - $k$ —— 该钻井中穿过的岩层数（$0 \leqslant k \leqslant n$）； - $s_1, s_2, \ldots, s_k$ —— 钻井自上而下依次穿过的岩层编号。 钻井按 $x$ 坐标递增顺序给出。 保证至少存在一个满足条件的解。

输出一行，包含 $n$ 个整数 $p_1, p_2, \ldots, p_n$，表示一种可能的岩层从上到下的顺序。每个岩层编号从 $1$ 到 $n$，且在序列中恰好出现一次。 并且应满足以下条件：对于岩层编号 $p_j$，在整个区间中，它**不会出现在**岩层 $p_1, p_2, \ldots, p_{j-1}$ **之上**，也不会出现在岩层 $p_{j+1}, \ldots, p_n$ **之下**。 若存在多种可能的排列，输出任意一种即可。

### 样例解释 题目中的示意图对应此样例。 对于该样例，答案 `2 3 1 4` 也是正确的。 请注意，样例测试不属于子任务 1 的范围。 ### 数据范围 本题包含五个子任务。每个子任务的测试集独立计分，只有当该组所有测试均通过时，才能获得该子任务的分数。 | 子任务 | 限制条件 | 分值 | |:--:|:--:|:--:| | 1 | $1 \leqslant n, m \leqslant 1000$，每口钻井都穿过了其位置下方的所有岩层 | 20 | | 2 | $1 \leqslant n, m \leqslant 1000$ | 20 | | 3 | $1 \leqslant n, m \leqslant 30\,000$，钻井中岩层编号的总数不超过 $10^6$ | 20 | | 4 | $1 \leqslant n, m \leqslant 10^5$，钻井中岩层编号的总数不超过 $10^5$ | 20 | | 5 | $1 \leqslant n, m \leqslant 10^5$，钻井中岩层编号的总数不超过 $10^6$ | 20 |