We are given N people (indexed from 0 to N - 1) and M pair of friends among them, and we would like to assign each person to a line of N apartments so that the sum of the distance between friends is minimized.
We illustrate the assignment with examples. Let N be 8 and we assign them to apartment as in (0, 1, 2, 3, 4, 5, 6, 7). If person 0 and 5 are friends, then the distance between them is 5. Furthermore, if 1 and 6 are also friends, then the sum of the distance of this ordering is now 10. In this case, we can assign people as (0, 5, 1, 6, 2, 3, 4, 7), so the sum of the distance becomes 2, which is the minimum sum of the distance.
Subtasks
20 points. N = 5.
70 points. N <= 10.
10 points. N = 11. For this subtask, you need to “cut” the search once you realize that any further selection from this variation will not be better than the best one you have seen. That is, if you know the current best solution is 6, and if your current selection already has a sum of distance 8, then it is meaningless to continue.
Input Format
There is only one test case. The first line contains two integers, N and M, then the next M lines contain two integers between 0 to N-1, for example, 0 1 indicates that 0 and 1 are friends.
N > 1
M > 0
Output Format
Print a line containing one integer which is the minimized sum of the distance of the ordering.
Task Description
We are given N people (indexed from 0 to N - 1) and M pair of friends among them, and we would like to assign each person to a line of N apartments so that the sum of the distance between friends is minimized.
We illustrate the assignment with examples. Let N be 8 and we assign them to apartment as in (0, 1, 2, 3, 4, 5, 6, 7). If person 0 and 5 are friends, then the distance between them is 5. Furthermore, if 1 and 6 are also friends, then the sum of the distance of this ordering is now 10. In this case, we can assign people as (0, 5, 1, 6, 2, 3, 4, 7), so the sum of the distance becomes 2, which is the minimum sum of the distance.
Subtasks
20 points. N = 5.
70 points. N <= 10.
10 points. N = 11. For this subtask, you need to “cut” the search once you realize that any further selection from this variation will not be better than the best one you have seen. That is, if you know the current best solution is 6, and if your current selection already has a sum of distance 8, then it is meaningless to continue.
Input Format
There is only one test case. The first line contains two integers, N and M, then the next M lines contain two integers between 0 to N-1, for example, 0 1 indicates that 0 and 1 are friends.
N > 1
M > 0
Output Format
Print a line containing one integer which is the minimized sum of the distance of the ordering.
Sample Input 1
Sample Output 1
Sample Input 2
Sample Output 2