## Connect the Dots

View as PDF

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

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 turns, he does the following steps:

1. First, choose a number .
2. For every dot currently on the canvas (exclude new dots painted this turn), paint new dots.
3. Connect all of the new dots and the chosen dot such that they form a cycle of length .
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 used for each turn. Please help hewmatt10!

#### Input Specification

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

The next lines contain 2 integers , indicating that dots and are connected. Any 2 dots and will not be connected more than once.

#### Output Specification

If the painting is valid, output integers on their on line. Otherwise, output baf.

#### 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 and has a length of . There are cycles ; ; ; created in the second turn, each with a length of .