Description

Krahc is painting KPH.

KPH is abstract. He can be represented as a graph with $n$ vertices and $m$ edges.

Krahc's draft is abstract. It only contains the line art, so Krahc asks you to add colors.

Krahc's colors are abstract, so each color can be abstracted as a positive integer.

Krahc is abstract, so he hates monochromatic cycles. He hopes you can ensure that there are no monochromatic cycles in the painting while helping him color it.

Krahc doesn't like abstract, so he hopes you can provide the least abstract coloring scheme.

The definition of abstractness is abstract. A scheme is less abstract than another if for the first edge that differs in color, its color is smaller.

Format

Input

The first line contains two integers $n,m\,(1\leq n,m\leq 10^6)$, representing the number of vertices and edges of KPH.

The next $m$ lines, each containing two integers $u_i,v_i\,(1\leq u_i,v_i\leq n)$, represent an edge between vertices $u_i$ and $v_i$.

Output

$m$ lines, each containing one integer, representing the color of the corresponding edge in the input. The colors should be positive integers, and there should be no monochromatic cycles in the graph.

It is guaranteed that a solution exists.

Samples

2 2
1 2
1 2

1
2