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

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

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

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~.