Задача 4. Антенна ≡

Условие

Для связи с Землёй членам экспедиции на Марс необходимо собрать антенну. Антенна в разобранном состоянии представляет собой n фрагментов, i-й фрагмент представляет собой штангу длиной s_i сантиметров, на которой закреплены m_i перекладин. Каждый фрагмент содержит хотя бы одну перекладину.

У каждой штанги есть начало, в котором расположен штекер, и конец, в котором расположено гнездо. Любые две штанги можно последовательно соединить, присоединив начало одной к концу другой. Для каждой перекладины известно расстояние от начала её штанги в сантиметрах. Для i-го фрагмента это расстояние может быть от 0 до s_i, значение 0 означает, что перекладина находится непосредственно в начале штанги, значение s_i — что она находится непосредственно в конце штанги. Толщиной перекладин и размерами штекера и гнезда следует пренебречь.

На рисунке показаны три фрагмента антенны из первого примера и отмечены расстояния от начала штанги до перекладины.

Чтобы корректно собрать антенну, необходимо соединить в некотором порядке все n фрагментов, при этом расстояние между любыми двумя соседними перекладинами должно быть одинаковым.

На рисунке показан корректный способ соединить фрагменты в первом примере.

К сожалению, члены экспедиции забыли инструкцию по сборке антенны на Земле, а передать её на Марс не представляется возможным — ведь антенна ещё не собрана. Помогите исследователям!

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

Формат входных данных

В первой строке дано одно число n — количество фрагментов.

Далее дано описание n фрагментов. В первой строке описания фрагмента даны два целых числа m_i и s_i — количество перекладин и длина штанги в i-м фрагменте. В следующей строке даны m_i целых чисел p_{i, j} — позиции перекладин, p_{i, j} равно расстоянию в сантиметрах от начала штанги до j-й перекладины на ней.

Формат выходных данных

Если собрать антенну указанным образом возможно, в первой строке выведите Yes, а во второй строке выведите перестановку чисел от 1 до n — номера фрагментов в порядке, в котором их следует соединить, начало каждого следующего фрагмента в этом порядке присоединяется к концу предыдущего фрагмента. Если существует несколько подходящих ответов, можно вывести любой из них.

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

Ограничения

1 ≤ n ≤ 100 000, 1 ≤ m_i ≤ 100 000, 0 ≤ s_i ≤ 10⁹

0 ≤ p_{i, 1} < p_{i, 2} < …  < p_{i, mi} ≤ s_i

Сумма всех m_i не превышает 100 000.

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Примеры тестов

3
1 7
3
1 8
6
2 8
1 6

Yes
2 1 3 

1
1 7
5

Yes
1

1
3 10
2 5 9

No

3
1 5
3
1 3
3
1 6
3

No

4
1 5
0
1 0
0
1 3
3
1 0
0

Yes
3 2 4 1 

Разбор

Подзадача 1

Для того, чтобы решить первую подзадачу, можно перебрать, в каком порядке нужно соединить фрагменты. Всего существует n! таких вариантов. Для каждого варианта можно вычислить позиции всех перекладин и проверить, подходит ли такой вариант.

Подзадача 2

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

Общая идея

Как во второй подзадаче, оставим на каждом фрагменте только первую и последнюю перекладины. Пусть на i-м фрагменте первая перекладина находится на расстоянии l_i от начала, а последняя — на расстоянии r_i от конца. Научимся проверять, существует ли порядок фрагментов, при котором расстояние между соседними перекладинами будет равно d. Пусть такой порядок существует, обозначим его q₁, q₂, …, q_n. Тогда должно выполняться r_qi + l_qi + 1 = d (1 ≤ i ≤ n − 1), значит l_qi + 1 = d − r_qi. Рассмотрим граф, вершинами которого являются все целые числа. Проведем ориентированное ребро из l_i в d − r_i для всех i. Заметим, что искомый порядок существует тогда и только тогда, когда в построенном графе существует Эйлеров путь. Поиск Эйлерова пути (и проверка существования) является стандартным алгоритмом.

Например, в первом тесте из примеров, l₁ = 3, r₁ = 4, l₂ = 6, r₂ = 2, l₃ = 1, r₃ = 2. В ответе на тест, d = 5. Построим граф по этим данным:

Рядом с вершинами написаны соответствующие им числа, а рядом с ребрами — номера соответствующих им фрагментов. Видно, что последовательность ребер 2, 1, 3 является Эйлеровым путем.

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

Подзадача 4

Чтобы решить четвертую подзадачу, нужно заметить, что по принципу Дирихле всегда будет существовать хотя бы один фрагмент, содержащий хотя бы две перекладины. Поэтому, если искомый порядок существует, расстояние d между соседними перекладинами должно быть равно расстоянию между соседними перекладинами на этом фрагменте. Воспользуемся алгоритмом и проверим, подходит ли данное d.

Подзадача 3

Чтобы решить третью подзадачу, можно перебрать два варианта:

• Если фрагмент номер 1 не будет стоять самым последним, то можно перебрать номер фрагмента i, который будет стоять сразу после фрагмента 1, и проверить d = r₁ + l_i.
• Если фрагмент номер 1 будет стоять самым последним, то фрагмент номер 2 не будет стоять последним. Можно перебрать номер фрагмента i, который будет стоять после фрагмента 2, и проверить d = r₂ + l_i.

Таким образом, мы проверим O(n) вариантов, каждый за время O(n). Итого, решение работает за O(n²).

Подзадача 5

Чтобы решить пятую подзадачу, можно проверить все значения d от 0 до 200. Дополнительно ускорить решение можно, проверяя только значения d от 0 до ⌊100 ⋅ nn − 1⌋.

Подзадача 6

Наконец, чтобы решить задачу на полный балл, нужно было научиться проверять только O(1) различных вариантов d. Рассмотрим пары (l_qi, r_qi + 1) и отсортируем их в порядке возрастания l. Заметим, что так как суммы значений в каждой паре равны, значения r будут убывать. Среди всех значений l в рассмотренных парах не присутствует ровно одно, соответствующее первому фрагменту. Аналогично, среди всех значений r отсутствует значение, соответствующее последнему фрагменту. Таким образом, можно отсортировать все значения l в порядке возрастания, все значения r в порядке убывания и проверить 4 варианта значения d: сумма одного из двух минимальных значений l и одного из двух максимальных значений r.