미지의 다각형

정 N각형의 각 꼭짓점에는 1부터 N까지의 정수가 하나씩, 중복 없이 붙어 있다. 다각형 안에는 서로 교차하지 않는 M개의 대각선이 그려져 있으며, 두 선분이 끝점을 공유하는 경우는 교차로 보지 않는다.

다각형의 N개 변과 M개 대각선에 대해, 각 선분이 잇는 두 꼭짓점의 정수 쌍만 순서 없이 기록했다. 이 선분 목록이 주어질 때, 원래 다각형의 둘레를 따라 꼭짓점에 붙은 정수들을 구하라.

첫째 줄에 정수 N과 M이 주어진다. N은 3 이상 10,000 이하이고, M은 0 이상 N-3 이하이다.

이어서 N+M개의 줄에 선분 하나의 양 끝점에 붙은 정수 두 개가 주어진다.

첫째 줄에 다각형의 둘레를 따라 만나는 N개의 정수를 공백으로 구분해 출력한다.

항상 1을 먼저 출력하고, 가능한 두 방향 중 두 번째 정수가 더 작은 방향을 선택한다.