Задача №112806. Счета дядюшки Скруджа
Дядюшка Скрудж известен своей жадностью. Когда-то давно он завел аж \(n\) банковских счетов. На каждый из этих счетов ежедневно приходит фиксированная положительная сумма в \(b_i\) долларов. Таким образом, через \(t\) дней на \(i\)-м счету находится \(t\times{}b_i\) долларов.
Сегодня Билли, Вилли и Дилли решили проучить своего дедушку. Они украли из его бухгалтерии всю информацию о числах \(b_i\). Теперь дядюшка Скрудж даже не сможет посмотреть сумму на каждом из счетов, ведь число \(b_i\) является также паролем для \(i\)-го из них. Но ребята понимают, что это слишком жестокая шутка над Скруджем, поэтому они решили дать ему шанс и сделали \(m\) подсказок.
Каждая подсказка состоит в следующем: ребята выбирают какой-либо день, некоторое множество счетов и сообщают Скруджу номера этих счетов и сумму на них в этот день. Номер дня ребята ему не говорят.
Теперь Скрудж может попытаться восстановить числа \(b_i\) по имеющимся подсказкам. Он в отчаянии: для него это слишком сложная задача, поэтому он попросил вас помочь ему.
В первой строке входного файла даны два целых числа \(n\), \(m\) (\(1 \le n \le 100\,000, 1 \le m \le 100\,000\)) — количество счетов дядюшки Скруджа и количество подсказок Билли, Вилли и Дилли. В следующих \(2 m\) строках описаны подсказки дяде Скруджу: сначала идет целое число \(k_i\) (\(1 \le k_i \le n\)) — количество счетов, для которых ребята записали их состояние в некоторый день, в следующей строке идут \(2 k_i\) целых чисел \(c_{i,j}\), \(x_{i,j}\) (\(1 \le c_{i,j} \le n, 1 \le x_{i,j} \le 10^{18}\)) — номер счета и сумма на нем. Гарантируется, что для каждой подсказки \(c_{i,j}\) различны.
Гарантируется, что сумма \(k_i\) не превосходит \(3\cdot 10^5\).
В первой строке выведите «NO», если решения не существует и «YES» в противном случае. Если решение существует, следующая строка должна содержать \(n\) целых чисел \(b_i\) (\(1 \le b_i \le 10^{18}\)) — сколько долларов приходит на \(i\)-й счет ежедневно. Если решений, удовлетворяющих всем подсказкам, несколько, выведите любое.
3 2 2 1 6 2 9 1 1 8
YES 2 3 1
5 3 2 1 4 2 6 2 2 12 3 8 3 2 9 3 6 4 3
YES 2 3 2 1 1
3 2 2 1 6 2 9 2 1 9 2 6
NO
В первом примере номер дня для первой подсказки равен \(3\), для второй \(4\), считая от дня отрытия счетов. Во втором примере номер дня для первой подсказки равен \(2\), для второй \(4\), для третьей \(3\), считая от дня отрытия счетов. В третьем примере решения не существует.
Первая группа тестов состоит из тестов, для которых выполняется ограничение \(x_{i,j} \le 100\,000\). Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет \(50\) баллов.
Вторая группа тестов состоит из тестов, для которых выполняются полные ограничения. Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет \(50\) баллов.