Поликарп разрабатывает RPG-видеоигру, главный герой которой сражается с монстрами и ищет сокровища в подземельях. Сейчас Поликарп добавляет в игру одно из подземелий.
Подземелье состоит из \(n\) комнат, соединенных \(m\) двусторонними туннелями, используя которые, можно добраться из любой комнаты в любую другую комнату. Комнаты охраняются монстрами (количество монстров в \(i\)-й комнате равно \(a_i\)), а в туннелях можно найти золотые монеты (количество монет в \(i\)-м туннеле равно \(w_i\)). \(i\)-й двусторонний туннель соединяет комнаты \(v_i\) и \(u_i\).
Поликарп уже определил количество монет в каждом туннеле (значения \(w_i\) уже известны), и теперь он пытается распределить монстров по комнатам (значения \(a_i\) пока не известны). Поликарп хочет выбрать количество монстров в каждой комнате так, чтобы выполнялись два условия:
- количество монет в туннеле, соединяющем комнаты \(x\) и \(y\), равно минимум из \(a_x\) и \(a_y\). То есть, для каждого туннеля \(i\) выполняется \(w_i = \min (a_{v_i}, a_{u_i})\);
- суммарное количество монстров во всех комнатах как можно меньше. То есть, значение \(a_1 + a_2 + \dots + a_n\) — минимально возможное.
Помогите Поликарпу выбрать значения \(a_1\), \(a_2\), ..., \(a_n\), или скажите ему, что это невозможно и в плане подземелья что-то необходимо поменять.
Выходные данные
Выведите ответ на каждый набор входных данных следующим образом:
Если невозможно найти значения \(a_1\), \(a_2\), ..., \(a_n\), удовлетворяющие всем условиям, в единственной строке выведите NO. Иначе выведите YES в первой строке и \(n\) целых чисел \(a_1\), \(a_2\), ..., \(a_n\) во второй строке. Если возможных ответов несколько, выведите любой из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3 2
1 2 1
2 3 1
5 7
3 2 7
3 4 9
1 5 5
1 2 5
4 1 5
4 2 7
3 1 5
4 4
1 2 5
3 2 2
4 1 3
3 4 4
|
YES
1 1 1
YES
5 7 9 9 5
NO
|