Artifacts

Kostya is on a quest to find the new Babylon and has discovered ( n ) pieces of a map. There are ( q ) constraints that specify which pieces must be used together. Each constraint is given by two numbers, ( a ) and ( b ), indicating that pieces ( a ) and ( b ) can only be used in conjunction.

Input

The first line contains two integers, ( n ) and ( q ), where ( 1 \leq n, q \leq 3 \times 10^5 ).The following ( q ) lines each contain a pair of integers representing the constraints.

Output

Print ( n ) integers, where the ( i )-th integer represents the minimum number of map pieces required to use the ( i )-th piece.

Examples