커널 스케줄러

시간 제한2초메모리 제한1024 MB

요약

작업 n개와 의존 관계 m개가 주어졌을 때, 사이클이 생기지 않도록 의존 관계를 m/2개 이상 골라 번호를 출력합니다.

난이도: 보통10점 중 5점
유형: 그래프, 위상 정렬, 그리디
정답자: 아직 제출이 없습니다

문제

새로운 운영체제의 스케줄링 모듈을 개발하고 있다고 하자. 이 모듈은 실행할 작업 $n$ 개와 작업 사이의 의존 관계를 입력받아 실행 순서를 정한다.

더 정확히 말하면, 작업에는 1부터 $n$ 까지 번호가 매겨져 있다. 의존 관계는 $m$ 개 주어지며, $i$ 번째 의존 관계는 두 수 $a_i$ , $b_i$ 로 표현된다. 이는 작업 $a_i$ 를 작업 $b_i$ 보다 먼저 실행해야 한다는 뜻이다.

순환 의존이 생기는 경우도 있다. 작업 $t_1$ 이 $t_2$ 보다 먼저, $t_2$ 가 $t_3$ 보다 먼저, ..., $t_{k-1}$ 이 $t_k$ 보다 먼저, 그리고 $t_k$ 가 $t_1$ 보다 먼저 실행되어야 하는 상황이다. 순환 의존은 스케줄링을 불가능하게 만드므로, 남은 의존 관계에 순환이 없도록 주어진 의존 관계 일부를 제거해야 한다.

다만 원래 정보를 일부 보존하려면 원래 의존 관계를 최소 $m/2$ 개는 남겨야 한다. 이 작업을 수행하는 프로그램을 작성하라.

입력

첫 줄에 $n$ 과 $m$ 이 주어진다 ( $2 \le n \le 10^5$ , $1 \le m \le 3 \cdot 10^5$ ). 이어지는 $m$ 개의 줄에는 각각 의존 관계를 나타내는 두 수 $a_i$ , $b_i$ 가 주어진다 ( $1 \le a_i, b_i \le n$ , $a_i \ne b_i$ ).

출력

조건을 만족하는 의존 관계의 부분집합이 존재하면 첫 줄에 YES, 없으면 NO를 출력한다. YES인 경우 둘째 줄에 선택한 의존 관계의 개수 $k$ 를 출력하고( $k$ 는 $m/2$ 이상이어야 한다), 셋째 줄에 선택한 의존 관계의 번호 $k$ 개를 출력한다. 번호는 입력 순서대로 1부터 $m$ 까지 매겨져 있다.

예제3

예제 1
입력
```
3 3
1 2
2 3
3 1
```
예상 출력
```
YES
2
1 2
```
예제 2
입력
```
2 5
1 2
1 2
1 2
2 1
2 1
```
예상 출력
```
YES
3
1 2 3
```
예제 3
입력
```
4 4
1 2
2 3
2 4
3 4
```
예상 출력
```
YES
4
1 2 3 4
```