빵집 줄 순서
시간 제한1초메모리 제한128 MB
친구 관계가 주어질 때, 정해진 삽입 규칙에 따라 사람들이 줄을 서서 최종 줄이 1부터 N까지가 되도록 하는 도착 순서를 찾거나 불가능함을 판별합니다.
문제
제빵사 크루흐코는 아주 맛있는 빵을 만든다. 빵집 문이 열리기 전부터 사람들은 길게 줄을 서며, 줄은 다음 규칙으로 만들어진다.
새 사람이 도착하면, 먼저 이미 줄에 서 있는 사람 중 자기 친구가 있는지 확인한다. 친구가 한 명 이상 있다면, 빵집 입구에 가장 가까운 친구 바로 앞에 선다. 줄 안에 친구가 아무도 없다면, 줄의 맨 뒤에 선다.
사람들은 1, 2, ..., N번으로 번호가 붙어 있으며, 어떤 두 사람이 친구인지 주어진다. 친구 관계는 서로에게 동일하게 적용된다.
예를 들어 N = 4이고 친구 관계가 1-2, 1-3, 3-4, 도착 순서가 (2, 4, 3, 1)이라면 줄은 다음과 같이 만들어진다.
2가 도착한다. 줄은(2)이다.4가 도착한다.4는2와 친구가 아니므로 줄의 맨 뒤에 선다. 줄은(2, 4)이다.3이 도착한다.3은4와 친구이므로4바로 앞에 선다. 줄은(2, 3, 4)이다.1이 도착한다.1은2,3과 친구이지만2가 입구에 더 가까우므로2바로 앞에 선다. 줄은(1, 2, 3, 4)이다.
최종 줄이 정확히 (1, 2, ..., N)이 되도록 하는 도착 순서를 아무거나 하나 구하라.
입력
첫째 줄에 사람의 수 N과 친구 관계의 수 M이 주어진다.
2 ≤ N ≤ 300 000, 1 ≤ M ≤ 1 000 000
다음 M개의 줄에는 친구 관계를 나타내는 두 정수 a, b가 주어진다. 두 정수는 모두 1 이상 N 이하이다.
출력
필요한 도착 순서를 공백으로 구분해 출력한다. 가능한 순서가 여러 개라면 아무거나 출력해도 된다.
그런 순서가 존재하지 않으면 -1만 출력한다.