21528번 - Магистраль <<Урал>> 스페셜 저지다국어

Планируется строительство новой магистрали <<Урал>>. Долговечность автомагистрали зависит от пластов пород, залегающих под ней. Пластом называется геологическое тело, состоящее из одной горной породы. 

Под будущей магистралью залегают $n$ горизонтальных пластов. Геологическое исследование позволило определить точки магистрали, под которыми начинается и заканчивается каждый из них. При этом порядок залегания пластов по глубине определить не удалось.   

В заданных местах вдоль планируемой магистрали пробурены вертикальные скважины. Каждая из них пересекает несколько верхних пластов, находящихся под точкой бурения. Для каждой скважины известно, в каком порядке располагаются пробуренные пласты сверху вниз, начиная от поверхности. Если скважина не пересекает какой-то из пластов, находящихся под точкой бурения, значит он проходит ниже дна скважины. 

Требуется написать программу, которая определяет возможный порядок залегания пластов по глубине, не противоречащий полученным данным.

Первая строка входного файла содержит целое число $n$ --- количество пластов. Пласты пронумерованы целыми числами от $1$ до $n$ в произвольном порядке. В $i$-й из следующих $n$ строк содержатся целые числа $l_i$ и $r_i$ ($0 \leqslant l_i < r_i\leqslant 10^9$) --- расстояния от начала магистрали до точек, под которыми начинается и заканчивается $i$-й пласт.

В следующей строке записано целое число $m$ --- количество скважин, в которых проводилось бурение. Следующие $m$ строк описывают результаты бурения: в каждой строке сначала указаны два целых числа $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$, описывающих возможный порядок залегания пластов сверху вниз. Среди чисел $p_1, p_2, \ldots , p_n$ каждый номер пласта должен встретиться ровно один раз. При этом пласт с номером $p_j$ не должен нигде проходить выше пластов с номерами $p_1, \ldots ,p_{j-1}$ или ниже пластов с номерами $p_{j+1}, \ldots , p_n$.                                                       

Если возможных расположений пластов несколько, выведите любое из них. 

• $1 \leqslant n,m \leqslant 10^5$.
• Суммарное количество пластов, найденных при бурении скважин, не более $10^6$.

Рисунок в условии соответствует примеру.

Для приведенного примера правильным также является ответ 2 3 1 4.

Обратите внимание, что тест из примера не соответствует подзадаче 1. Для того, чтобы решение было принято на проверку, оно должно проходить тест из примера, даже если решена только эта подзадача.