E. Вечный двигатель
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Разработчик Петр думает, что он изобрел вечный двигатель. А именно, у него есть много элементов, которые работают следующим образом.

У каждого элемента есть один регулятор, который можно установить на любое неотрицательное вещественное число. Если регулятор установлен на значение x, то данный элемент будет потреблять x2 единиц энергии в секунду. В то же время, любые два элемента, соединенные проводом, выделяют y·z единиц энергии в секунду, где y и z — значения, установленные на регуляторах этих двух элементов.

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

Гарантируется, что если существуют необходимые Петру положения регуляторов, то существуют и необходимые целочисленные положения, не превосходящие 106.

Входные данные

В каждом тесте задано несколько (не меньше одного) тестовых случаев. В первой строке находится одно целое число — количество тестовых случаев.

Перед данными для каждого тестового случая находится пустая строка. Первая строка данных содержит два целых числа n и m (1 ≤ n ≤ 105, 0 ≤ m ≤ 105) — количество элементов в схеме и количество проводов.

Далее следуют m строк, в каждой из которых находятся два целых числа a и b (1 ≤ a, b ≤ n) — очередная пара элементов, соединенных проводом. Никакой элемент не соединен проводом сам с собой, никакая пара элементов не соединена более чем одним проводом.

Гарантируется, что сумма величин n и сумма величин m по всем тестовым случаям не превосходят 105.

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

Выходные данные

Выведите ответ на каждый тестовый случай.

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

Если регуляторы нельзя установить требуемым образом, выведите одну строку «NO».

Пример
Входные данные
4
 
4 4
1 2
2 3
3 4
4 2
 
3 2
2 3
3 1
 
4 6
1 2
3 4
4 2
1 4
1 3
3 2
 
10 9
2 1
3 2
5 2
6 2
2 7
2 8
2 9
2 10
4 2
Выходные данные
YES
1 2 2 1
NO
YES
1 1 1 1
YES
1 5 1 1 1 1 1 1 1 1
Примечание

В первом тестовом случае можно установить регуляторы, например, следующим образом: на первом элементе установить 1, на втором и на третьем — 2, на четвертом — 1. Тогда потребляемая мощность будет равна 12 + 22 + 22 + 12 = 10 единиц энергии в секунду, а выделяемая — 1·2 + 2·2 + 2·1 + 2·1 = 10 единиц энергии в секунду. Значит, ответ — «YES».

Во втором тестовом случае установить регуляторы необходимым образом нельзя. Например, если на всех трех элементах установить регуляторы на 0.5, то потребляемая мощность будет равна 0.75 единиц энергии в секунду, а выделяемая — только 0.5 единиц энергии в секунду.