영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
시간 제한 1초 · 메모리 제한 512 MB
Problem
Given an undirected weighted graph, determine for each edge if it can be included in a minimum spanning tree.
Input
The first line has two integers n and m: the number of nodes and edges. The nodes are numbered 1,2,…,n.
The following m lines describe the edges. Each line has three integers a, b, w: there is an edge between nodes a and b with weight w.
You can assume that the graph is connected and simple and each edge appears at most once in the graph.
Output
For each edge in the input order, print YES if it can be included in the minimum spanning tree and NO otherwise.
Constraints
- 1 ≤ n ≤ 10^5
- 1 ≤ m ≤ 2 · 10^5
- 1 ≤ a,b ≤ n
- 1 ≤ w ≤ 10^9
예제
예제 1
5 6 1 2 4 1 3 2 2 4 2 3 4 1 3 5 3 4 5 3
NO YES YES YES YES YES