Appleby Contest '20 P4 - Philosophy Class

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 2.0s
Python 4.0s
Memory limit: 1G

Problem type

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 N potential topics that may be tested (numbered from 1 to N), and there are M pairs of topics (a_1, b_1), (a_2, b_2), \ldots, (a_M, b_M) that are related. And in order to pass, Ray must know a pair of topics (c, d) (where c \neq d) that are related so he can write about both of them on 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:

2 \le N \le 3\,000

1 \le M \le 3\,000

a_i \neq b_i for all 1 \le i \le M

Subtask 1 [10%]

N, M \le 10

Subtask 2 [30%]

N \le 500

Subtask 3 [60%]

No additional constraints.

Input Specification

The first line contains the integers N, M.

The next M lines each contain a pair of integers a_i, b_i.

Output Specification

If no set of topics exists that satisfies Ray's constraints, output only -1 on a single line.

Otherwise, let S be the smallest set of topics that satisfies Ray's constraints, and s_1, s_2, \ldots, s_k be the elements of S in increasing order.

On the first line, output the size of S.

On the second line, output s_1, s_2, \ldots, s_k.

If multiple possibilities exist for s_1, s_2, \ldots, s_k, output the lexicographically least one. A sequence x is lexicographically smaller than a sequence y if for some j, x_i=y_i for all i < j and x_j < y_j (in other words, the two sequence are identical up to a certain point, at which x is smaller than y).

Sample Input 1

6 6
2 5
5 3
2 3
2 6
3 6
1 5

Sample Output 1

2 3 5

Sample Explanation 1

While S=\{2, 3, 6\} would also satisfy Ray's requirements, the sequence 2,3,5 is lexicographically smaller.

Sample Input 2

5 4
1 5
2 5
3 5
4 5

Sample Output 2



There are no comments at the moment.