Perpetual Motion Machine
Contest: VK Cup 2017 - Finals
Difficulty rating: 3100
Tags: constructive algorithms, dp, graphs, trees

Developer Petr thinks that he invented a perpetual motion machine. Namely, he has a lot of elements, which work in the following way.

Each element has one controller that can be set to any non-negative real value. If a controller is set on some value x, then the controller consumes x2 energy units per second. At the same time, any two elements connected by a wire produce y·z energy units per second, where y and z are the values set on their controllers.

Petr has only a limited number of wires, so he has already built some scheme of elements and wires, and is now interested if it's possible to set the controllers in such a way that the system produces at least as much power as it consumes, and at least one controller is set on the value different from 0. Help him check this, and if it's possible, find the required integer values that should be set.

It is guaranteed that if there exist controllers' settings satisfying the above conditions, then there exist required integer values not greater than 106.

Input format:
There are several (at least one) test cases in the input. The first line contains single integer — the number of test cases.

There is an empty line before each test case. The first line of test case contains two integers n and m (1 ≤ n ≤ 105, 0 ≤ m ≤ 105) — the number of elements in the scheme and the number of wires.

After that, m lines follow, each of them contains two integers a and b (1 ≤ a, b ≤ n) — two elements connected by a wire. No element is connected with itself, no two elements are connected by more than one wire.

It is guaranteed that the sum of n and the sum of m over all test cases do not exceed 105.

For hacks you can only use tests with one test case.

Output format:
Print answer for each test case.

For each test case print "YES" if it's possible to set the controllers in such a way that the consumed power is not greater than the power produced, and the required values on the next line. The settings should be integers from 0 to 106, inclusive, and at least one value should be different from 0. If there are multiple answers, print any of them.

If it's not possible to set the controllers in the required way, print one line "NO".

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the first example it's possible to set the controllers in the required way, for example, in the following way: set 1 on the first element, set 2 on the second and on the third, set 1 on the fourth. The consumed power is then equal to 12 + 22 + 22 + 12 = 10 energy units per second, the produced power is equal to 1·2 + 2·2 + 2·1 + 2·1 = 10 energy units per second. Thus the answer is "YES".

In the second test case it's not possible to set the controllers in the required way. For example, if we set all controllers to 0.5, then the consumed powers equals 0.75 energy units per second, while produced power equals 0.5 energy units per second.

Example input:
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

Example output:
YES
1 2 2 1
NO
YES
1 1 1 1
YES
1 5 1 1 1 1 1 1 1 1

Editorial:
By default, all vertices contain 0. We will solve problem in few steps, getting answer for our question in different cases.
1. Graph contains cycle. In this case, solution exists, all vertices of cycle contain 1, sum would be 0.
2. Graph contains vertex with degree more than 3. Solution exists, this vertex has 2 and its neighbours 1. Sum will be 22 + deg(v) - 2 * deg(v) ≤ 0 when deg(v) ≥ 4.
3. Graph contains more than one vertex of degree 3. In this case we can reduce to previous case: we put 2 in the between these vertices and ones in other neighboors. Doing this, we "contract" path between vertices to one with the number 2 and obtain vertex of degree 4.
4. Graph contains just one vertex of degree 3. It is the most complicated point in our solution. We just state this and prove it later.Statement: There is only one vertex with degree 3, with 'tails' of sizes p - 1, q - 1 и r - 1 (length of the tail = how many vertices lay on it). In this case expression can take only non-positive values if $$\frac{1}{p} + \frac{1}{q} + \frac{1}{r} \leq 1$$.
5. All graph's vertices have degree less than 3. This case can be easily reduced to previous one, having p = 1.
We are going to prove this by two ways.
First way: Let's look on tail, sized k, having form of the bamboo. Numbers in vertices are ai and have sum A. We are going to minimize A. As one can see,
Let ak = S, d1 = a1, d2 = a2 - a1, d3 = a3 - a2, ..., dk = ak - ak - 1. Тогда
While
We will use induction for proof. Base (n = 1) is evident. Step n → n + 1: $$f(x) = \frac{(S-x)^2}{n} + x^2$$ – optimal sum of squares if one of n + 1 numbers is x. We shall minmize this function. This is nearly equal to derivative being zero. $$-2 \frac { S - x } { n } + 2 x = 0 \Rightarrow S - ( n + 1 ) x = 0 \Rightarrow x = \frac { S } { n + 1 }$$, what we wanted to prove.
Now we get back to construction where are three tails of sizes p, q и r are connected to 3-degree vertex. Number in 3-degree vertex is S, value of the whole graph is D, and values of tails are A, B и C. (2A - S2) + (2B - S2) + (2C - S2) = 2D + S2. If we fix S, when, as it was shown before optimal values of tails are i$$2A - S^2 = \frac{S^2}{p}$$, $$2B - S^2 = \frac{S^2}{q}$$, $$2C - S^2 = \frac{S^2}{r}$$. We have $$( \frac { 1 } { p } + \frac { 1 } { q } + \frac { 1 } { r } - 1 ) S ^ { 2 } = 2 D$$. It means that D ≤ 0 can be only if $$\frac{1}{p} + \frac{1}{q} + \frac{1}{r} \leq 1$$.
Second way:
Let the tail of size p have numbers in vertices x1, x2, ... xp - 1 counting from the leaf, size q - y1, y2, ... yq - 1, size r - z1, z2, ... zr - 1. Root we will define as v = xp = yq = zr.
Let
We want to compute S = v2 + Ax + Ay + Az.
One can see that
Actually, if we calculate this expression, we will have
$$2 A _ { x } = 2 x _ { 1 } ^ { 2 } - 2 x _ { 1 } x _ { 2 } + \frac { 1 } { 2 } x _ { 2 } ^ { 2 } + \frac { 3 } { 2 } x _ { 2 } ^ { 2 } - 2 x _ { 2 } x _ { 3 } + \frac { 2 } { 3 } x _ { 3 } ^ { 2 } + \cdots - 2 x _ { p - 1 } x _ { p } + \frac { p - 1 } { p } x _ { p } - \frac { p - 1 } { p } v$$
Each term with xi2 features once on both adjacent terms and gives the sum $$\frac { i - 1 } { i } x _ { i } ^ { 2 } + \frac { i + 1 } { i } x _ { i } ^ { 2 } = \frac { 2 i } { i } x _ { i } ^ { 2 } = 2 x _ { i } ^ { 2 }$$
When,
Because all F ≥ 0, we should have other expression not greater than zero. However, v ≠ 0, because in this case for having all squares zero all numbers would be zero. Because of this, $$\frac{1}{p} + \frac{1}{q} + \frac{1}{r} \leq 1$$.
Conclusion:
Necessity of this criterion is proved. Sufficiency can be seen from definition F in the second proof - we should put arithmetic progressions on all tails.
In case of graph having form of bamboo, we have $$1 + \frac{1}{q} + \frac{1}{r} - 1 \leq 0$$, equal to $${ \frac { 1 } { q } } + { \frac { 1 } { r } } \leq 0$$ while q, r ≥ 1, what is obviously impossible. So answer is always «NO».
All mentioned above is made with few depth-first searches, so complexity of this solution is O(V + E).