Informatica Online Judge

  태이근 [2103 / 0837]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 3   Total Tried : 112


The Champion of this Problem (C++) : gs16022 - 93ms / 1629byte
My Best Submission (C++) : N/A

[koistudy.net (unkonwn)]
Writer ID : [gs16022]

Background

영화 "테이큰" 을 보고 감명받은 우리의 황태근 사감 선생님께서는 테이큰과 같은 추격영화를 만들고 싶어졌다.

영화의 제목은 자신의 이름은 본 딴 "태이근"이며 무단외출범 규민이와 그를 추격하는 황태근 사감 선생님에 관한 영화이다.

이 영화의 하이라이트는 나무가 N개 있는 숲에 숨은 규민이를 마취총으로 쏴 잡는 내용이다.

규민이는 처음 N개의 나무 중 어디에 숨었는지 알 수 없다. 이 때, 사감 선생님은 나무에 마취총을 쏠 수 있고, 그 나무 뒤에 규민이가 있었다면 규민이가
쓰러지며, 없었다면 규민이는 몰래 이웃한 나무로 도망친다. (쏘기 전에 있던 위치에 남지는 못한다)
이웃된 나무가 없는 경우는 주어지지 않는다.

황태근 사감 선생님은 규민이가 어디 있는지 모르기 때문에 몇 개의 나무들을 골라 순서대로 쏘려고 한다.

그 나무들을 차례대로 사격한 뒤에 규민이가 처음에 어떤 나무 뒤에 있었든 최종적으로 마취총에 맞을 수 있게 총을 쏠 것이다.

하지만 황태근 선생님은 영화가 루즈해지는 것을 바라지 않고 계시기 때문에 최대한 사격횟수를 최소화하여 규민이를 쏴야한다.

또, 다양한 시나리오가 있어야 재밌는 장면을 선택할 수 있으므로, 사격횟수를 최소화해서 규민이를 잡는 경우의 수를 알고 싶다.

황태근 선생님은 빨리 "태이근"을 찍고 퇴근을 하고 싶기 때문에 여러분에게 1회 무단외출 허용권과 함께 도움을 요청했다.

황태근 선생님의 퇴근을 도와주자.

Input

첫 번째 줄에는 나무의 개수 N (1<=N<=20) 과 이웃한 나무의 쌍 M(0<=M<=190)이 입력된다.
나무는 0번부터 N-1번까지 번호가 부여된다.
그 다음 줄부터는 M개의 줄에 0이상 N-1이하의 정수 a, b가 공백을 사이에 두고 입력된다.
이는 a와 b나무가 이웃해있다는 것을 뜻하며 a->b, b->a 로 이동하는 것 모두 가능하다.

Output

최악의 경우 규민이를 잡지 못할 경우에 "Sad Ending" 을 출력한다.
그렇지 않을 경우 첫 번째 줄에 최소 사격 수 S를 출력한다.
두 번째 줄에는 사격을 해야하는 S개의 나무를 공백을 사이에 두고 순서대로 출력한다.
만약 최소 사격 수가 같은 여러 방법이 있다면 나무의 번호가 사전 순으로 가장 빠른 순으로 출력한다.
세 번째 줄에는 최소 사격 수가 같은 방법의 개수를 10억 9로 나눈 나머지를 출력한다.

IO Example

입력 예시 1
2 1
0 1

출력 예시 1
2
0 0
2

예시 설명 1

0을 두 번 쏠 경우 처음에 0에 있었을 땐 첫 발에 맞고, 처음에 1에 있었다면 첫 발 사격 이후 0으로 이동하여 두 번째 사격에 반드시 맞는다.

입력 예시 2
3 3
0 1
1 2
2 0

출력 예시 2
Sad Ending

예시 설명 2
어떤 식으로 사격을 해도 규민이가 반드시 피할 수 있는 시작 위치가 있다.

입력 예시 3
4 3
0 1
2 3
1 3

출력 예시 3
4
1 3 3 1
2

예시 설명 3

처음에 0 에 있었을 경우

첫 발 쏜 이후에 1로 이동
두 번째 발 쏜 이후에 0, 3 로 이동
세 번째 발에 3으로 이동한 경우는 죽고 아니면 1로 이동함
네 번째 발에 1에 있었으므로 죽음

처음에 1 에 있었을 경우

첫 발에서 총에 맞음

처음에 2 에 있었을 경우

첫 발 쏜 이후에 3으로 이동
두 번째 쏜 이후에 죽음

처음에 3 에 있었을 경우

첫 발 쏜 이후에 2나 1로 이동
2로 이동했으면 두 번째 발 이후로 3으로 이동, 세 번째 발에 죽음
1로 이동했으면 두 번째 발 이후로 0, 3으로 이동 3으로 이동했으면 세 번째 발에 죽음
0으로 이동했으면 세 번째 발 이후로 1로 이동, 네 번째 발에 죽음

이 순서대로 쏜다면 처음에 어디에 있었든 반드시 죽게 된다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]