30568번 - Kernel Scheduler 스페셜 저지다국어

문제

You are developing the scheduling module for the new operating system. This module takes $n$ tasks to be executed and the dependencies between them and then puts them in a certain order for execution.

More formally, there are $n$ tasks numbered from 1ドル$ to $n$. You are also given $m$ dependencies numbered from 1ドル$ to $m$; $i$-th of them is described by two numbers --- $a_i$ and $b_i,ドル meaning that the task $a_i$ should be executed before the task $b_i$.

In some cases, there are cyclical dependencies --- situations when according to the dependencies given some task $t_1$ should be executed before $t_2,ドル $t_2$ before $t_3,ドル \ldots, and $t_{k-1}$ before $t_k$ and $t_k$ before $t_1$. Cyclical dependencies create a problem for scheduling, so you decided to remove some of the given dependencies in such a way that the resulting set does not contain any cyclical ones.

However, you still need to keep at least $m/2$ original dependencies to preserve some of the original information. You are to write the program performing this task.

입력

• One line containing the numbers $n$ and $m$ (2ドル \le n \le 10^5,ドル 1ドル \le m \le 3 \cdot 10^5$).
• $m$ further lines, each containing two numbers $a_i$ and $b_i$ (1ドル \le a_i, b_i \le n,ドル $a_i \ne b_i$), describing the corresponding dependency between two tasks $a_i$ and $b_i$.

출력

The first line should should contain YES in case the desired subset of dependencies exists, and NO otherwise.

In the YES case second line should contain the number $k$ of the selected dependencies (please note that $k$ should be at least $m/2$) and the third line should contain $k$ numbers --- the ids of the selected dependencies. They are numbered from 1ドル$ to $m$ in the order given in the input.

제한

힌트