#437 Finding dfs tree

Statement

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

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

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

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

조건을 만족하는 부모 수열 $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은 유효한 부모 수열이다.

Sample 1

Input

Output

-1 1 1 2 2 3

$1$ 번 정점을 루트로 잡고 빨간색 간선들을 트리 간선으로 선택할 수 있다. 파란색 간선들은 모두 자손에서 조상으로 향한다. 이 구조는 본문의 그림과 같다.

Sample 2

Input

Output

-1

조건을 만족하는 루트 있는 스패닝 트리가 존재하지 않는다.