시리얼 2

Farmer John의 소들은 아침으로 시리얼을 먹는 것을 가장 좋아한다. 소들은 식욕이 커서 한 끼에 시리얼 한 상자를 통째로 먹는다.

농장에 $M$종류의 시리얼이 배송되었다 $(2\le M\le 10^5)$. 각 종류의 시리얼은 상자가 하나뿐이다. $N$마리의 소 $(1\le N\le 10^5)$는 각자 가장 좋아하는 시리얼과 두 번째로 좋아하는 시리얼이 있다. 시리얼을 고를 기회가 주어지면 소는 다음과 같이 행동한다.

1. 가장 좋아하는 시리얼의 상자가 남아 있으면 그것을 가져가고 떠난다.
2. 그렇지 않고 두 번째로 좋아하는 시리얼의 상자가 남아 있으면 그것을 가져가고 떠난다.
3. 그렇지도 않으면 실망하여 음매 하고 울며 시리얼을 가져가지 않고 떠난다.

소들의 순서를 최적으로 정했을 때 굶는 소의 최소 수를 구하라. 또한 그 최소 수를 달성하는 $N$마리 소의 순열을 하나 구하라.

첫째 줄에 공백으로 구분된 두 정수 $N$과 $M$이 주어진다.

$1\le i\le N$에 대해 $i$번째 줄에는 $i$번째 소가 가장 좋아하는 시리얼과 두 번째로 좋아하는 시리얼을 나타내는 두 정수 $f_i$와 $s_i$가 공백으로 구분되어 주어진다. ($1\le f_i,s_i\le M$이고 $f_i\neq s_i$)

굶는 소의 최소 수를 출력하고, 이어서 그 최소 수를 달성하는 $1\ldots N$의 순열을 출력한다. 최소 수를 달성하는 순열이 여러 개라면 그중 아무거나 출력해도 된다.

이 경우에는 소 $8$마리와 시리얼 $10$종류가 있다.

처음 세 소는 가장 좋아하는 시리얼이 서로 겹치지 않으므로 마지막 다섯 소와 독립적으로 풀 수 있다.

처음 세 소가 [1,2,3] 순서로 고르면 소 $1$은 시리얼 $2$를, 소 $2$는 시리얼 $3$을 고르고 소 $3$은 굶는다.

처음 세 소가 [1,3,2] 순서로 고르면 소 $1$은 시리얼 $2$를, 소 $3$은 시리얼 $3$을, 소 $2$는 시리얼 $4$를 고르므로 세 소 모두 굶지 않는다.

물론 처음 세 소가 모두 굶지 않는 다른 순열도 있다. 예를 들어 [3,1,2] 순서로 고르면 소 $3$은 시리얼 $2$를, 소 $1$은 시리얼 $1$을, 소 $2$는 시리얼 $3$을 고르므로 소 [1,2,3]은 모두 굶지 않는다.

마지막 다섯 소 중에서는 적어도 한 마리가 반드시 굶어야 함을 보일 수 있다.