As a student of Dr. Panev Philosophy class, Ridiculous Ray will have to write an in-class essay next week.
Ridiculous Ray has not been studying however, and needs to learn the topics from scratch. Additionally, as he is very lazy, he wants you to help him find the minimum effort to become prepared.
On the test, there are potential topics that may be tested (numbered from to ), and there are pairs of topics that are related. And in order to pass, Ray must know a pair of topics (where ) that are related so he can write about both of them in the essay.
Additionally, to make the test more difficult, Dr. Panev has decided to remove one of the potential topics on the day of the test (which means that Ray cannot write about it). And as Ridiculous Ray wants to be prepared for every possible scenario, he wants you to find the smallest set of topics he can study such that no matter which topic is removed, he will still have studied a pair of related topics that he can write about (or tell him that it is impossible).
For all subtasks:
Subtask 1 [10%]
Subtask 2 [30%]
Subtask 3 [60%]
No additional constraints.
The first line contains the integers .
The next lines each contain a pair of integers .
If no set of topics exists that satisfies Ray's constraints, output only
-1 on a single line.
Otherwise, let be the smallest set of topics that satisfies Ray's constraints, and be the elements of in increasing order.
On the first line, output the size of .
On the second line, output .
If multiple possibilities exist for , output the lexicographically least one. A sequence is lexicographically smaller than a sequence if for some , for all and (in other words, the two sequences are identical up to a certain point, at which is smaller than ).
Sample Input 1
6 6 2 5 5 3 2 3 2 6 3 6 1 5
Sample Output 1
3 2 3 5
Sample Explanation 1
While would also satisfy Ray's requirements, the sequence is lexicographically smaller.
Sample Input 2
5 4 1 5 2 5 3 5 4 5
Sample Output 2