## Connect the Dots

is playing connect the dots! Because he has no friends, he has to play connect the dots with himself. first starts with 1 dot on his canvas. Every turn, for \(T\) turns, he does the following steps:

- First, choose a number \(C_i\ (3 \le C_i)\).
- For every dot currently on the canvas (exclude new dots painted this turn), paint \(C_i - 1\) new dots.
- Connect all of the new dots and the chosen dot such that they form a cycle of length \(C_i\).
- Repeat steps 2-3.

has sold these canvases for millions of dollars. He has made so much money that other people has started making counterfeit paintings! , determined to destroy his enemies, wants to see whether their paintings follow his painting process. Specifically, wants to know whether the painting is invalid, or if it is valid, the \(C_i\) used for each turn. Please help !

#### Input Specification

The first line will contain 2 integers \(N, M\), the number of dots and lines on the canvas, respectively. It is guaranteed that \(N\) is larger than all \(C_i\).

The next \(M\) lines contain 2 integers \(U, V\ (1 \le U, V \le N)\), indicating that dots \(U\) and \(V\) are connected. Any 2 dots \(U\) and \(V\) will not be connected more than once.

#### Output Specification

If the painting is valid, output \(T\) integers \(C_i\) on their on line. Otherwise, output `baf`

.

#### Subtasks

##### Subtask 1 [30%]

\(1 \le N \le 10^3\)

\(0 \le M \le 5 \cdot 10^3\)

##### Subtask 2 [70%]

\(1 \le N \le 10^5\)

\(0 \le M \le 2 \cdot 10^6\)

#### Sample Input

```
12 15
1 2
1 3
2 3
1 4
4 5
5 6
6 1
2 7
7 8
8 9
9 2
3 10
10 11
11 12
12 3
```

#### Sample Output

```
3
4
```

#### Explanation for Sample

The cycle created in the first turn is composed of nodes \(1, 2, 3\) and has a length of \(3\). There are \(3\) cycles \(1, 4, 5, 6\); \(2, 7, 8, 9\); \(3, 10, 11, 12\); created in the second turn, each with a length of \(4\).

## Comments