Appleby Contest '20 P4 - Philosophy Class

View as PDF

Submit solution


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

Author:
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 NN potential topics that may be tested (numbered from 11 to NN), and there are MM pairs of topics (a_1, b_1), (a_2, b_2), \dots, (a_M, b_M)(a_1, b_1), (a_2, b_2), \dots, (a_M, b_M) that are related. And in order to pass, Ray must know a pair of topics (c, d)(c, d) (where c \ne dc \ne d) 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).

Constraints

For all subtasks:

2 \le N \le 3\,0002 \le N \le 3\,000

1 \le M \le 3\,0001 \le M \le 3\,000

a_i \ne b_ia_i \ne b_i for all 1 \le i \le M1 \le i \le M

Subtask 1 [10%]

N, M \le 10N, M \le 10

Subtask 2 [30%]

N \le 500N \le 500

Subtask 3 [60%]

No additional constraints.

Input Specification

The first line contains the integers N, MN, M.

The next MM lines each contain a pair of integers a_i, b_ia_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 SS be the smallest set of topics that satisfies Ray's constraints, and s_1, s_2, \dots, s_ks_1, s_2, \dots, s_k be the elements of SS in increasing order.

On the first line, output the size of SS.

On the second line, output s_1, s_2, \dots, s_ks_1, s_2, \dots, s_k.

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

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 S=\{2, 3, 6\}S=\{2, 3, 6\} would also satisfy Ray's requirements, the sequence 2,3,52,3,5 is lexicographically smaller.

Sample Input 2

5 4
1 5
2 5
3 5
4 5

Sample Output 2

-1

Comments

There are no comments at the moment.