New Megacity

You are part of a large project to design a new megacity that connects $n$ cities. There are $m$ candidate roads, and each road has a construction cost. All cities must be connected at the minimum total cost, which means they must form a minimum spanning tree (MST). Not all roads matter equally, though. Classify each road into one of three types:

• Type 1: The road is included in every MST.
• Type 2: The road is included in at least one MST, but not in every MST.
• Type 3: The road is not used in any MST.

The first line contains two integers $n$ and $m$, the number of cities and the number of candidate roads. The bounds are $2 \le n \le 100\,000$ and $n - 1 \le m \le \min(100\,000, n(n - 1)/2)$. Each of the next $m$ lines contains three integers $x$, $y$, and $z$, meaning that a road connects cities $x$ and $y$ and costs $z$. Here $x \ne y$, $1 \le x, y \le n$, and $1 \le z \le 100\,000$. No two cities are connected by more than one road. The input always has at least one MST.

Print $m$ lines. The $i$-th line contains a single integer, 1, 2, or 3, which is the type of the $i$-th road in input order.