문제

찬우는 알로하 회원을 대상으로 알고리즘 토너먼트를 개최했다.

알고리즘 토너먼트는 다음과 같은 방식으로 진행된다.

1. 알로하 회원 명이 참가하며, 총 경기의 게임이 진행된다.
2. 각 게임에서는 매칭된 사람끼리 1:1 대결 이후 승자와 패자를 겨룬다. (무승부는 존재하지 않는다.)
3. 공정한 게임을 위해 사람들을 랜덤하게 매칭한다. 따라서 게임을 한 판도 안 하는 회원이 있을 수 있고, 같은 상대와 여러 판 하는 회원도 있을 수 있다.

찬우는 알고리즘을 잘하는 소수의 회원들은 알고리즘 토너먼트에 재미를 느끼는 반면, 그렇지 못한 사람들은 즐기지 못한다는 것을 알게 됐다. 따라서 찬우는 모두에게 즐거움을 주고자 회원 모두가 적어도 한 번은 이기도록 모든 게임의 결과를 조작하기로 결정했다.

하지만 내년 알로하 회장을 준비하는 찬우는 바쁘기 때문에 게임을 어떻게 조작해야 할지 몰라 당신에게 도움을 구했다.

모든 회원이 적어도 한 번은 이길 수 있도록 만들 수 있는지, 만약 만들 수 있다면 각 게임에서 누가 이겨야 하는지 구해 보자.

만약 게임의 승패를 어떻게 설정해도 한 번도 못 이기는 회원이 생긴다면 -1을 출력해라.

입력

첫째 줄에 알로하 회원 수를 뜻하는 정수 과 진행하는 게임 수 이 공백으로 구분되어 주어진다. 알로하 회원은 번부터 번까지 번호로 구분 가능하다.

둘째 줄부터 개 줄에 걸쳐 매칭된 결과가 주어진다. 그중 번째 줄에는 번째 게임에서 매칭된 두 회원의 번호 와 가 공백 하나로 구분되어 주어진다.

출력

모든 회원이 적어도 한 번 이길 수 있다면 번, 번, , 번 게임에서 이기게 되는 회원 번호를 한 줄에 하나씩 출력해라. 조건을 만족하는 게임 결과가 여러 가지라면 그중 아무거나 출력한다.

만약 게임의 승패를 어떻게 설정해도 한 번도 못 이기는 회원이 생긴다면 출력 첫 줄에 -1을 출력해라. (이후 출력은 존재하지 않는다.)