Minimise Difference CodeChef Problem Code: MINDIFF1 Full Solution

 Minimise Difference Problem Code: MINDIFF1

Answer is given at last

Read problem statements in Mandarin Chinese, Russian, and Vietnamese as well.

You're given a simple undirected graph G with N vertices and M edges. You have to assign, to each vertex i, a number Ci such that 1≤Ci≤N and ∀i≠j,Ci≠Cj.

For any such assignment, we define Di to be the number of neighbours j of i such that Cj<Ci.

You want to minimise maxi∈{1..N}Di−mini∈{1..N}Di.

Output the minimum possible value of this expression for a valid assignment as described above, and also print the corresponding assignment.

Note:

The given graph need not be connected.

If there are multiple possible assignments, output anyone.

Since the input is large, prefer using fast input-output methods.

Input Format

First line will contain T, number of testcases. Then the testcases follow.

The first line of each test case contains two integers N,M - the number of vertices and edges in the graph respectively.

The next M lines each contain two integers - X,Y, denoting that there exists an edge between vertex X and vertex Y.

Output Format

The output of each test case consists of two lines:

The first line contains the minimum possible value of the expression described above.

The second line contains N space separated integers - the ith of which is Ci in the corresponding assignment.

Constraints

1≤T≤1000

1≤N,M≤3⋅105

1≤X≠Y≤N

The sum of N across test cases does not exceed 3⋅105.

The sum of M across test cases does not exceed 3⋅105.

Sample Input 1 

3

5 7

1 2

1 3

1 4

2 3

2 4

2 5

3 5

5 4

1 2

2 3

3 4

4 5

3 3

1 2

2 3

1 3

Sample Output 1 

2

1 2 3 4 5 

1

5 3 1 2 4

2

3 2 1

Explanation

Test Case 1: The following assignment is optimal:

C1=1

C2=2

C3=3

C4=4

C5=5

We can see that 3 has two neighbours with smaller values - 1 and 2. Vertex 5 is also its neighbour, but has a larger value. Therefore, D3=2.

Similarly, we can calculate:

D1=0

D2=1

D3=2

D4=2

D5=2

Therefore, maxi∈{1..N}Di−mini∈{1..N}Di = 2−0 = 2.

Test Case 2: The following assignment is optimal:

C1=5

C2=3

C3=1

C4=2

C5=4

The values of D are:

D1=1

D2=1

D3=0

D4=1

D5=1

Therefore, maxi∈{1..N}Di−mini∈{1..N}Di = 1−0 = 1.

                                                                                                                               Click Here For Answer