In geometry class, the teacher drew a circle with many chords on it. These chords do not overlap, but some of them intersect. You wanted to copy the drawing to study it at home, but unfortunately, the duty student erased it after class. Fortunately, you accurately recorded the number of chords and which pairs of chords intersect.

Now, you want to reconstruct the drawing as much as possible. At the same time, you also want to know the maximum number of chords you can select such that no two selected chords intersect.

Input

The first line contains two positive integers $n$ and $m$, representing the number of chords and the number of intersecting pairs of chords, respectively. The chords are numbered from $1$ to $n$.

The next $m$ lines each contain two positive integers $a$ and $b$, indicating that chord $a$ and chord $b$ intersect.

Output

The output consists of two lines.

The first line outputs $2n$ positive integers, representing the relative order of the two endpoints of each chord on the circle in counter-clockwise order, where the two endpoints of the $i$-th chord are both represented by the number $i$.

The second line outputs one positive integer, representing the maximum number of chords that can be selected such that no two intersect.

Examples

Input 1

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

Output 1

1 2 3 1 4 2 5 4 3 5  
2

The data for this problem is randomly generated. Any pair of chords not appearing in the input does not intersect. If the output is invalid, no points will be awarded.

For $10\%$ of the data, $1 \leq n \leq 3$;

For $30\%$ of the data, $1 \leq n \leq 8$;

For $40\%$ of the data, $1 \leq n \leq 12$;

For $60\%$ of the data, $1 \leq n \leq 15$;

For $75\%$ of the data, $1 \leq n \leq 17$;

For $95\%$ of the data, $1 \leq n \leq 18$;

For $100\%$ of the data, $1 \leq n \leq 20$, $1 \leq m \leq 40$.