50063. Friend Distance

I'm a slow walker, but I never walk backwards.

Task Description

We are given $N$ people and $M$ pair of friends among them, and we would like to assign people to a line of $N$ chairs so that the maximum distance between two friends is minimized.

We illustrate the seating with examples. We use the first $N$ uppercase letters to indicate people. Let $N$ be $8$ and we seat people as ABCDEFGH, with A and F are friends, then the distance between them is $5$. Furthermore, if A and H are also friends, then the maximum distance of this ordering is now $7$.

Subtask

  • 95pt. $1\lt N \leq 10$.

  • 5pt. $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. If your current selection already has a distance 8, then it is meaningless to continue.

Input Format

There is only one test case. The first line contains two integers indicated $N$ and $M$, then the next $M$ lines contain two uppercase letter (A, B, C, ...), for example, A B indicates that A and B are friends.

Output Format

There are two line. the first line contains one integer which is the minimized maximum distance, and the second line output the ordering of that minimized distance which is the first one in lexicographical order.

Sample Input 1

3 1
A B

Sample Output 1

1
A B C

Sample Input 2

8 10
A B
A F
B C
B G
C D
D E
D G
F G
F H
H E

Sample Output 2

3
A B C F G D H E

Discussion