32824번 - New Megacity 다국어

문제

You are involved in a huge project to design a new megacity connecting $n$ cities using a given set of $m$ potential roads, each with an associated cost. All cities should be connected with the minimum total cost, that is, they form a Minimum Spanning Tree (MST). However, not all roads are equally important. Your job is to determine the importance of each road on the following categories:

• Type 1: The road is included in every possible MST that connects all cities. This means that this road is essential for the optimal solution.
• Type 2: The road appears in at least one MST but does not in all.
• Type 3: The road is never used in any MST; it does not contribute to the least costly connection of all cities.

Given a road network of $n$ cities with $m$ roads with associated costs, write a program to output the type of each road.

입력

Your program is to read from standard input. The input starts with a line containing two integers $n$ and $m,ドル where $n$ is the number of cities (2ドル ≤ n ≤ 100,000円$) and $m$ is the number of potential roads ($n - 1 ≤ m≤\min(100,000,円 n(n - 1)/2)$).

In the following $m$ lines, the $i$-th road is given by three integers $x,ドル $y,ドル $z$ where $x$ and $y$ are the cities connected by the road (1ドル ≤ x, y ≤ n,ドル $x \ne y$), and $z$ is the cost of building that road (1ドル ≤ z ≤ 100,000円$). Each pair of cities is connected by at most one road, that is, there are no multiple edges between the same pair of cities.

It is guaranteed that at least one MST always exists for the given input.

출력

Your program is to write to standard output. Print $m$ lines. The $i$-th line should contain a single integer representing the type of the $i$-th road (1, 2, or 3), in the same order as the input.

제한

힌트