Servers#7065
The corporation has servers, each identified by a unique natural number from to . Each server occupies one shelf in a server cabinet. There are a total of shelves in the cabinet, also numbered from to . Due to equipment upgrades, the servers need to be rearranged. The challenge is that certain pairs of servers must be directly connected by cables, and the length of each cable is determined by the difference in the shelf numbers where the connected servers are placed.
Your task is to arrange the servers to minimize the total cable length required.
Determine the minimum total cable length needed for this arrangement and provide one possible configuration that achieves this.
The first line contains a natural number (2 \le N \le 20). The second line contains the number of server pairs that need to be directly connected.
The following lines each contain a pair of distinct natural numbers, representing the servers that need to be connected. Each pair is listed only once.
The first line should display the minimum possible total cable length. The second line should show a permutation of the numbers 1, 2, \ldots, N, indicating the optimal server arrangement: the number in the -th position represents the server to be placed on the -th shelf.
Example 1