# Minimise Difference Solution codechef

Table of Contents

# Minimise Difference Solution codechef

You’re given a simple undirected graph  with  vertices and  edges. You have to assign, to each vertex , a number  such that  and .

For any such assignment, we define  to be the number of neighbours  of  such that .

You want to minimise .

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

Note: Minimise Difference Solution codechef

• 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 Minimise Difference Solution codechef

• First line will contain , number of testcases. Then the testcases follow.
• The first line of each test case contains two integers  – the number of vertices and edges in the graph respectively.
• The next  lines each contain two integers – , denoting that there exists an edge between vertex  and vertex .

### Output Format Minimise Difference Solution codechef

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  space separated integers – the  of which is  in the corresponding assignment.

### Constraints Minimise Difference Solution codechef

• The sum of  across test cases does not exceed .
• The sum of  across test cases does not exceed .

### Sample Input 1 Minimise Difference Solution codechef

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 Minimise Difference Solution codechef

2
1 2 3 4 5
1
5 3 1 2 4
2
3 2 1


### Explanation Minimise Difference Solution codechef

Test Case : The following assignment is optimal:

We can see that  has two neighbours with smaller values –  and . Vertex  is also its neighbour, but has a larger value. Therefore, .

Similarly, we can calculate:

Therefore,  =  = .

Test Case : The following assignment is optimal:

The values of  are:

Therefore,  =  = .