BOJ 8632 Byteland

문제 링크:

문제 내용

정점 $n$개, 간선 $m$개인 무방향 그래프가 주어집니다. 각각의 간선에 대해, 그 간선이 적어도 하나의 최소 스패닝 트리에 포함되는지 판별하세요.

입력

첫 줄에는 정점의 개수 $n$과 간선의 개수 $m$이 주어집니다. ($2 \le n \le 7000$, $1 \le m \le 300\;000$)

다음 $m$줄에는 각 간선의 양 끝점의 번호 $x$, $y$와 그 간선의 가중치 $w$가 주어집니다. ($1 \le x, y \le n$, $1 \le w \le 100\;001$) $w$의 범위에 주의하세요.

출력

$1 \le i \le m$에 대해 $i$번째 줄에 입력의 $i$번째 간선이 적어도 하나의 스패닝 트리에 포함된다면 TAK, 아니라면 NIE를 출력합니다.

문제 풀이