BOJ 16659 LED-led Paths

문제 링크:

문제 내용

$V$개의 정점과 $E$개의 유향 간선을 갖는 사이클이 없는 그래프가 주어집니다. 각각의 간선을 RGB 중 한 가지 색으로 칠해서, 한 가지 색으로만 이루어진 최장 경로의 길이가 $42$를 초과하지 않도록 하세요.

입력

첫 줄에는 $V$와 $E$가 주어집니다. ($2 \le V \le 50\;000$, $1 \le E \le 200\;000$)

다음 $E$줄에 걸쳐서 유향 간선이 한 줄에 하나씩 주어집니다. 각 간선은 출발 정점 $a$와 도착 정점 $b$ 순서로 주어집니다. ($1 \le a, b \le V$, $a \neq b$)

임의의 정점 쌍에 대해 두 정점을 직접 잇는 간선은 최대 한 개입니다.

출력

문제의 조건에 맞게 모든 간선을 아무 방법으로 색칠했을 때, 각 간선의 색깔을 입력에서 주어진 순서대로 한 줄에 하나씩 출력합니다.

문제 풀이