Far Graphs

All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
Consider a positive even integer L and N distinct integers a_{1}, a_{2}, ..., a_{N} such that  a_{i}  a_{j}  ≤ L for all 1 ≤ i, j ≤ N. Now, we define a far graph induced by L and a_{1..N} as a graph with N vertices (numbered 1 through N) satisfying the following condition: for each pair of vertices u and v, there is an undirected edge between u and v if and only if  a_{u}  a_{v}  ≥ L/2.
Given a simple graph G, you should find integers L and a_{1}, a_{2}, ..., a_{N} such that G is a far graph induced by them, or determine that no such integers exist.
Input
 The first line of the input contains a single integer T denoting the number of testcases. The description of T test cases follows.
 The first line of each test case contains two spaceseparated integers N and M denoting the number of vertices and the number of edges in the input graph G respectively.
 Each of the following M lines contains two spaceseparated integers u and v denoting an edge between vertices u and v.
Output
For each test case: If it's impossible to choose valid numbers L and a_{1}, a_{2}, ..., a_{N} such that the graph G is a far graph, print a single line containing a single string "No" (without quotes).
 Otherwise, print two lines.
 The first line should contain a single string "Yes" (without quotes).
 The second line should contain N+1 spaceseparated integers L, a_{1}, a_{2}, ..., a_{N} such that G is a far graph and the following constraints hold:
 1 ≤ L ≤ 2 · 10^{9}
 L is even
 all a_{i} are distinct
 10^{9} ≤ a_{i} ≤ 10^{9} for each valid i
 If there are multiple solutions, you may output any one.
Constraints
 1 ≤ T ≤ 5
 2 ≤ N ≤ 1000
 1 ≤ M ≤ 10^{6}
 1 ≤ u, v ≤ N
 the graph will not contain multiple edges or selfloops
Example
Input: 3 3 3 1 2 2 3 3 1 7 8 1 6 1 4 3 2 6 3 3 4 4 5 4 7 5 6 4 6 1 2 1 3 1 4 2 3 2 4 3 4 Output: Yes 2 12 10 11 Yes 20 7 12 1 20 4 17 10 No
Explanation
Example case 1: There are 3 vertices connected in a cycle. We can take L = 2, a_{1} = 12, a_{2} = 10 and a_{3} = 11. Since  12  10  ≥ 1,  10  11  ≥ 1, and  11  12  ≥ 1, this means that there are edges between pairs of vertices (1, 2), (2, 3) and (3, 1) respectively. This is exactly the given graph, so the answer is "Yes", and we print these values.
Example case 2: The figure below shows the graph with the values mentioned in the sample output.
We take L = 20. You can check that there is an edge between two vertices if and only if the values differ by at least L/2 = 10.
Example case 3: No matter what values we try, we will not be able to get the input graph as the induced far graph. Hence the answer is "No".
Author:  admin3 
Tester:  kingofnumbers 
Editorial  https://discuss.codechef.com/problems/FARGRAPH 
Tags  admin3, cook90, graphtheory, mediumhard 
Date Added:  18122017 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions