문제
정올이의 아이들은 세상에서 시리얼이 제일 맛있다고 한다! 정올이의 아이들은 시리얼을 너무도 좋아해서 한끼에 시리얼 한 상자를 다 먹어버린다.
최근 제과회사 로테오리옹은 M개의 다른 종류의 시리얼(2≤M≤105)을 출시했다. 불행히도 각 시리얼은 한 상자 씩만 있는데, N명의 아이들이(1≤N≤105) 각각은 좋아하는 시리얼과 두 번째로 좋아하는 시리얼이 있을 때, 선택할 수 있는 시리얼이 주어지면 아이들은 아래와 같은 과정의 행동을 실행한다.
1. 아이가 가장 좋아하는 시리얼 상자가 아직 남아 있다면 가져간다.
2. 그렇지 않고, 아이가 두 번째로 좋아하는 시리얼 상자가 아직 남아 있다면 그것을 가져간다.
3. 그렇지 않으면 시리얼을 먹지 않고 떠난다.
위와 같은 과정을 실행 하였을 때, 시리얼을 먹지 못해 배고파하는 아이들의 최소 수를 출력하고, 이 최소값을 달성하는 N명의 아이들의 순열을 출력하시오.
입력
첫 번째 줄에는 N과 M이 주어진다.
두 번째 줄부터 N줄에 걸쳐 i번째 줄에 i번째 아이가 제일 선호하는 시리얼인 fi 와 두 번째로 선호하는 시리얼인 si (1≤fi,si≤M, fi≠si)가 주어진다.
출력
배고픈 아이들의 최소 수를 출력하고, 이 최솟값을 달성하는 1...N의 순열을 출력하시오.
답이 여러 개인 경우 그 중 하나만 출력하시오.
예제1
8 10
2 1
3 4
2 3
6 5
7 8
6 7
7 5
5 8
1
1
3
2
8
4
6
5
7
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을 선택한다. 이 경우 셋 중 누구도 굶지 않을 것이다.
마지막 다섯 명 중 적어도 한 명은 굶어야 한다.