새로운 메가시티

당신은 $n$개의 도시를 잇는 새로운 메가시티를 설계하는 대형 프로젝트에 참여하고 있다. 건설 후보 도로는 $m$개이며, 도로마다 건설 비용이 정해져 있다. 모든 도시를 최소 총비용으로 연결해야 하므로, 도로들은 최소 신장 트리(MST)를 이루어야 한다. 다만 도로마다 중요도는 다르다. 각 도로를 다음 세 종류 중 하나로 분류하라.

• 종류 1: 모든 MST에 포함되는 도로이다.
• 종류 2: 적어도 하나의 MST에 포함되지만, 모든 MST에 포함되지는 않는 도로이다.
• 종류 3: 어떤 MST에도 사용되지 않는 도로이다.

첫 줄에 도시의 수 $n$과 건설 후보 도로의 수 $m$이 정수로 주어진다. 제약은 $2 \le n \le 100\,000$, $n - 1 \le m \le \min(100\,000, n(n - 1)/2)$이다. 이어지는 $m$개의 줄에는 정수 $x$, $y$, $z$가 주어지며, 이는 도시 $x$와 도시 $y$를 잇는 도로의 건설 비용이 $z$라는 뜻이다. 여기서 $x \ne y$, $1 \le x, y \le n$, $1 \le z \le 100\,000$이다. 같은 두 도시를 잇는 도로는 하나를 넘지 않는다. 입력에는 항상 MST가 적어도 하나 존재한다.

$m$개의 줄을 출력한다. $i$번째 줄에는 입력에서 $i$번째 도로의 종류를 나타내는 정수 1, 2, 3 중 하나를 출력한다.