You are given connected undirected graph with n vertices and m edges.

Let's say that mapping between edges and positive integers $f(e)$ is good mapping if following conditions are true:

1. For each pair of edges $e_1$ and $e_2$ ($e_1 \neq e_2$) holds $f(e_1) \neq f(e_2)$;
2. Let's define the set of all edges incident to v as $N(v)$. If size of $N(v)$ is greater than 1, then $\gcd{f(e) \mid e \in N(v)} = 1$.

Your task is to find good mapping that $\max\limits_{e \in E}(f(e))$ is minimum as possible.

Input format

The first line contains three integers n and m ($2 \leq n \leq 2 \cdot 10^5$, $1 \leq m \leq 2 \cdot 10^5$) — number of vertices and number of edges, respectively.

Then m lines follow.

The i-th of them contains integers $a_i$ and $b_i$ ($1 \leq a_i, b_i \leq n$, $a_i \neq b_i$) describing edge $e_i$ connecting $a_i$ and $b_i$.

Output format

First line of output should contain single integer $\max\limits_{e \in E}(f(e))$ of your mapping f.

Then print m lines: the i-th of these lines should contain single integer $f(e_i)$.