잃어버린 배열
면접 대비시간 제한1초메모리 제한512 MB
min(X[Ai], X[Bi]) = Ci 형태의 M개 조건이 주어질 때, 모든 조건을 만족하는 양의 정수 배열 X를 하나 복원한다.
문제
Rar the Cat은 양의 정수 N개로 이루어진 배열 X를 가지고 있다. 그는 선생님이고, 자기 배열을 바탕으로 학생들에게 숙제를 내주려고 한다. 그의 반 학생들은 min 함수를 배웠고, Rar는 이것을 시험해 보고 싶어 한다. 그는 이미 M개의 숙제 문제를 냈고, 모두 다음과 같은 형태이다:
min(Xi, Xj) = ?
안타깝게도 Rar는 자기 배열을 잃어버렸다! M개의 숙제 문제와 답안지를 보고, Rar가 숙제 답안과 모두 맞는 배열 하나를 복원하도록 도와주자. 그러한 배열은 반드시 존재한다.
입력
프로그램은 표준 입력에서 읽는다.
입력의 첫 줄에는 2개의 수 N과 M이 주어진다.
다음 M줄에는 3개의 수 Ai, Bi, Ci가 주어진다. 모든 i = 1, 2, ..., M에 대해 min(XAi, XBi) = Ci이다.
출력
배열 X를 한 줄에 공백으로 구분하여 N개의 수로 출력한다. 답이 여러 개라면 그중 아무거나 출력해도 된다. X의 모든 원소는 1 이상 109 이하여야 한다.
제한
- 1 ≤ N, M ≤ 105
- 1 ≤ Ai, Bi ≤ N
- Ai ≠ Bi
- 1 ≤ Ci ≤ 109