DFS 트리 찾기

정점에 $1,2,\cdots,N$의 번호가 붙은 단순 방향 그래프 $G$가 주어진다. 모든 간선의 방향을 무시하면 그래프는 연결되어 있다.

$G$의 일부 간선을 골라 다음 조건을 만족하는 루트 있는 스패닝 트리를 만들려고 한다.

• 루트가 아닌 각 정점 $v$는 부모 $P_v$를 하나 가지며, 방향 간선 $P_v \to v$가 에 존재한다.

진조상은 자기 자신을 제외한 조상을 뜻한다.

아래 그림은 조건을 만족하는 한 예시이다. 빨간색 간선은 트리 간선이며 부모에서 자식으로 향한다. 파란색 간선은 트리에 속하지 않으며 자손에서 조상으로 향한다.

조건을 만족하는 부모 수열 $P_1,P_2,\cdots,P_N$을 구하여라. 존재하지 않으면 을 출력한다.

입력은 다음과 같은 형식으로 주어진다.

$N\ M$ $u_1\ v_1$ $u_2$

조건을 만족하는 트리가 존재한다면 한 줄에 $P_1,P_2,\cdots,P_N$을 공백으로 구분하여 출력한다. 루트의 부모는 로 출력해야 한다.

• $1 \leq N \leq 100\,000$.
• $0 \leq M \leq 100\,000$.
• $1\le {}_{}$ ().