25446번 - Povjerenstvo 서브태스크스페셜 저지다국어

문제

Do you know how hard it is to choose a set of people for the problem selection committee? No? Well do you know who does? Mr. Malnar, of course. By observing human interactions, the all-knowing Mr. Malnar has decided what the ideal choice should look like.

A total of $N$ people are being considered for the committee and $M$ relations between them have been recorded. A relation is described by an ordered pair $(a, b)$ representing the fact that person $a$ dislikes person $b$. Mr. Malnar defines a dislike circle to be a sequence of distinct people $x_1, x_2, \dots , x_k$ such that person $x_i$ dislikes person $x_{i+1},ドル for each 1ドル ≤ i ≤ k$ (it is assumed that $x_{k+1} = x_1$). Mr. Malnar noticed a peculiar property regarding the set of people in question: there is no dislike circle consisting of an odd number of people.

To minimize dissatisfaction with the choice of committee, Mr. Malnar is looking for a committee such that everyone within the committee agrees with each other and everyone outside of the committee is glad not to be in it. More precisely:

• There must not be two people within the committee such that one person dislikes the other.
• For each person outside the committee there should be someone in the committee who they dislike.

Can you find such a set of people?

입력

The first line contains positive integers $N$ and $M,ドル the number of people and number of relations between them, respectively.

The $i$-th of the following $M$ lines contains an ordered pair of positive integers $a_i$ and $b_i$ (1ドル ≤ a_i , b_i ≤ N$), representing the fact that person $a_i$ dislikes the person $b_i$. It holds that $a_i ≠ b_i$ for all $i = 1, 2, \dots , M$ and no ordered pair is listed twice.

The given relations will be such that there is no dislike circle consisting of an odd number of people.

출력

If it is not possible to choose a set of people satisfying the given conditions, in the only line print -1.

Otherwise, in the first line print a positive integer $K$ (1ドル ≤ K ≤ N$), the number of people in the committee. In the next line print $K$ distinct positive integers $p_1, p_2, \dots , p_K$ (1ドル ≤ p_i ≤ N$), the indices of the people which make up the committee.

If there is more than one solution, output any one of them.

제한

In all subtasks, it holds that 1ドル ≤ N ≤ 500,000円$ and 0ドル ≤ M ≤ 500,000円$.

서브태스크

힌트

The set of chosen people is shown in the output of each test case.

The first example is a valid test case for the first subtask and for the second subtask.

The second example is not a valid test case for the first subtask, but it is valid for the second subtask.

The third example is not a valid test case for the first subtask nor for the second subtask.