22960번 - 미팅 스페셜 저지

문제

이성 친구를 사귀고 싶어서 국렬이가 주선한 미팅에 신청한 남성 $N$명, 여성 $N$명이 있다.

서로에게 호감을 갖는 $M$개의 남녀의 쌍이 주어진다. 국렬이는 미팅에 참여한 남성들 중 임의로 몇 명을 선정해 미팅을 진행하려고 한다. 국렬이가 선정한 남성을 보고, 그들 중 적어도 한 명과 호감을 갖는 여성들은 미팅에 참가하게 된다. 만약 미팅에 참가한 남성의 수가 여성의 수보다 작거나 같다면 미팅은 원활하게 진행 될 것이다. 반대로 남성의 수가 더 많은 경우 미팅을 원활하게 진행할 수 없다. 그림의 예시 경우에는 2번째 남성과 3번째 남성을 선정했을 때, 이들과 호감을 갖는 여성이 2번째 여성 한 명이고, 남성의 수가 더 많기에 미팅이 원활하게 진행될 수 없다.

국렬이는 이 미팅의 주선자이지만 무적의 솔로 부대 출신이기에 남들이 잘되는 것을 원하지 않으므로 미팅이 원활하게 진행되는 것을 막고자 한다. 남녀 간의 호감 관계가 주어졌을 때, 미팅이 원활하게 진행되지 않도록 남성들을 선정해주자.

입력

첫 번째 줄에는 $N$과 $M$이 주어진다. (1ドル \le N \le 500,ドル 0ドル \le M \le N^2$)

다음 $M$개에 줄에 걸쳐서 두 개의 정수 $u$와 $v$가 주어진다. 이는 $u$번째 남성과 $v$번째 여성이 서로 호감을 갖고 있다는 의미다. 두 남녀 간의 관계는 최대 1번만 주어진다.

출력

미팅이 원활하게 진행될 수 없게 남성들을 선정할 수 있다면, 첫 번째 줄에 선정해야 하는 남성 수를 출력한다. 그 다음 줄에 선정해야 하는 남성의 번호를 출력한다. 가능한 방법이 여러 가지인 경우 아무거나 출력한다.

어떻게 남성들을 선정하더라도 미팅이 원활하게 진행될 수 있으면 첫 번째 줄에 -1을 출력한다.

제한

힌트