31841번 - Nogcd 스페셜 저지다국어

Boss, if $N≤30\, 000$, you should try to optimise the $N^2$ solution. (Friedrich Nietzsche)

Let $G$ be a undirected connected graph with $N$ nodes and $M$ edges. Label each of the $M$ edges with a distinct integer from $1$ to $M$. For each node with degree greater than $1$, the greatest common divisor of its incident edges' labels should be $1$.

The first line contains two integers $N$ and $M$.

The next $M$ lines contain two integers $u$ and $v$, representing two nodes that share an edge.

Print $M$ lines, each containing three integers $u$, $v$ and $c$ corresponding to an edge with label $c$ between $u$ and $v$.

• $1≤N≤10^5$
• $1≤M≤220\, 000$
• There are no self-loops or multiple edges in the graph.