DFS 트리 찾기

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

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

• 루트가 아닌 각 정점 $v$는 부모 $P_v$를 하나 가지며, 방향 간선 $P_v \to v$가 $G$에 존재한다.
• 루트 $r$에 대해서는 $P_r=-1$이다.
• 고른 $N-1$개의 간선 $P_v \to v$는 부모에서 자식 방향으로 향하는 루트 있는 스패닝 트리를 이룬다.
• 트리 간선으로 고르지 않은 모든 방향 간선 $u \to v$에 대해, $v$는 트리에서 $u$의 진조상이다.

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

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

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

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

$N\ M$ $u_1\ v_1$ $u_2\ v_2$ $\vdots$ $u_M\ v_M$

$i$번 간선은 $u_i$에서 $v_i$로 향한다.

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

가능한 답이 여러 가지라면 아무거나 출력해도 된다.

조건을 만족하는 트리가 존재하지 않는다면 한 줄에 -1을 출력한다.

$N=1$인 경우 한 개의 값 -1은 유효한 부모 수열이다.

• $1 \leq N \leq 100\,000$.
• $0 \leq M \leq 100\,000$.
• $1 \leq u_i,v_i \leq N$ ($1 \leq i \leq M$).
• $u_i \neq v_i$ ($1 \leq i \leq M$).
• $(u_i,v_i) \neq (u_j,v_j)$ ($1 \leq i < j \leq M$).
• 모든 간선의 방향을 무시한 그래프는 연결되어 있다.