Счета дядюшки Скруджа

시간 제한3초메모리 제한1024 MB

요약

각 힌트가 어떤 알 수 없는 날에 특정 계좌들의 잔액을 제시할 때, 모든 계좌의 일일 입금액을 복원하거나 해가 없음을 판정한다.

난이도: 보통10점 중 5점
유형: 그래프, DFS, 정수론, 수학
정답자: 아직 제출이 없습니다

문제

Дядюшка Скрудж известен своей жадностью. Когда-то давно он завел аж $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$ , для второй $4$ , считая от дня отрытия счетов. Во втором примере номер дня для первой подсказки равен $2$ , для второй $4$ , для третьей $3$ , считая от дня отрытия счетов. В третьем примере решения не существует.

예제3

예제 1
입력
```
3 2
2
1 6 2 9
1
1 8
```
예상 출력
```
YES
2 3 1
```

예제 2

입력

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
입력
```
3 2
2
1 6 2 9
2
1 9 2 6
```
예상 출력
```
NO
```