정점에 의 번호가 붙은 단순 방향 그래프 가 주어진다. 모든 간선의 방향을 무시하면 그래프는 연결되어 있다.
의 일부 간선을 골라 다음 조건을 만족하는 루트 있는 스패닝 트리를 만들려고 한다.
진조상은 자기 자신을 제외한 조상을 뜻한다.
아래 그림은 조건을 만족하는 한 예시이다. 빨간색 간선은 트리 간선이며 부모에서 자식으로 향한다. 파란색 간선은 트리에 속하지 않으며 자손에서 조상으로 향한다.
조건을 만족하는 부모 수열 을 구하여라. 존재하지 않으면 을 출력한다.
입력은 다음과 같은 형식으로 주어진다.
조건을 만족하는 트리가 존재한다면 한 줄에 을 공백으로 구분하여 출력한다. 루트의 부모는 로 출력해야 한다.
번 정점을 루트로 잡고 빨간색 간선들을 트리 간선으로 선택할 수 있다. 파란색 간선들은 모두 자손에서 조상으로 향한다. 이 구조는 본문의 그림과 같다.
조건을 만족하는 루트 있는 스패닝 트리가 존재하지 않는다.
번 간선은 에서 로 향한다.
가능한 답이 여러 가지라면 아무거나 출력해도 된다.
조건을 만족하는 트리가 존재하지 않는다면 한 줄에 -1을 출력한다.
인 경우 한 개의 값 -1은 유효한 부모 수열이다.
| 3 | 29 |
|
| 4 | 51 | 추가적인 제약이 없다. |
