Seating Arrangement for Maximum Friendships

You are given (n) guests and (m) friendships. Each friendship is given as a pair of guest IDs (u) and (v) (with (1 \leq u, v \leq n)). A friendship is satisfied if the two friends are seated consecutively in the arrangement. Your task is to determine an arrangement of all guests such that the number of satisfied friendships is maximized.

Note that if the guests form several disconnected components in the friendship graph, then if a component has (k) guests, at most (k-1) friendships can be satisfied within that component. Thus, the maximum possible number of satisfied friendships is [ \sum_{i=1}^{c} (|C_i| - 1), ] where (C_i) are the connected components of the friendship graph.

Any seating arrangement achieving this count is acceptable.

inputFormat

The first line contains two integers (n) and (m) separated by a space, where (n) is the number of guests and (m) is the number of friendships. Each of the next (m) lines contains two integers (u) and (v), representing a friendship between guest (u) and guest (v).

outputFormat

Output two lines. The first line contains the maximum number of satisfied friendships. The second line contains the seating arrangement -- a permutation of the integers from 1 to (n) such that the maximum number of friendships are satisfied. Separate the guest numbers by spaces.## sample

2 1
1 2

1
1 2