Олег живет в стране Банкополии. В стране n городов, некоторые пары городов соединены двунаправленными дорогами. Города пронумерованы от 1 до n. Всего в Банкополии m дорог, дорога номер i соединяет города ui и vi. Гарантируется. что из любого города можно добраться в любой другой по дорогам.
Олег хочет отметить целым числом каждый город. Предположим. отметка города i равна xi. Тогда для любой пары городов (u, v) условие |xu - xv| ≤ 1 должно выполняться тогда и только тогда, когда есть дорога, соединяющая u и v.
Олег задумался над вопросом, возможно ли так отметить города. Расставьте корректно отметки городам, или найдите, что это невозможно.
Выходные данные
Если невозможно отметить города. удовлетворив условию, выведите в единственной строке «NO» (без кавычек).
Иначе выведите «YES» (без кавычек) в первой строке. Во второй строке выведите n целых чисел x1, x2, ..., xn. Должно выполняться 1 ≤ xi ≤ 109 для всех i, кроме того, для любой пары (u, v) условие |xu - xv| ≤ 1 должно выполняться тогда и только тогда, когда есть дорога, соединяющая u и v.
Примечание
В первом примере x1 = 2, x2 = 3, x3 = x4 = 1 — корректная расстановка отметок. Действительно, (3, 4), (1, 2), (1, 3), (1, 4) — пары городов, разница отметок на которых не превосходит 1, и именно эти пары городов соединяются дорогами Банкополии.
Во втором примере разница отметок между любой парой городов не превосходит 1, все пары городов соединены дорогами.
В последнем примере невозможно расставить отметки так, чтобы удовлетворить условию.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 4
1 2
1 3
1 4
3 4
|
YES
2 3 1 1
|
|
2
|
5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
5 4
|
YES
1 1 1 1 1
|
|
3
|
4 3
1 2
1 3
1 4
|
NO
|