Informatica Online Judge

  뤼팽과 홈즈의 대결 [1121 / 0461]

Time Limit(Test case) : 3000(ms)
Number of users who solved : 4   Total Tried : 58


The Champion of this Problem (C++) : gs15120 - 73ms / 2666byte
My Best Submission (C++) : N/A

[koistudy.net (32nd 유재민)]

Background

괴도 뤼팽이 나타나 프랑스 왕실의 보물인 다이아몬드 목걸이를 훔쳐갔다.

의뢰를 받은 셜록홈즈는 괴도 뤼팽을 잡으려고 프랑스에 도착했고 곧 뤼팽이 숨어 있는 장소를 알아내었다.

그러나 뤼팽도 홈즈가 자신의 위치를 알고 있다는 사실을 알기에 빨리 배를 타고 외국으로 떠나려고 한다.

뤼팽이 곧 숨어있는 장소에서 떠나기 때문에 홈즈는 바로 뤼팽의 아지트로 갈 수 없으며 뤼팽의 목적지인 항구는 사람들이 너무 붐벼서 홈즈는 항구에서 뤼팽을 기다릴 수가 없다.

그래서 홈즈는 뤼팽의 아지트에서 항구로 갈 수 있는 길 중간에 있는 도시에서 잠복을 하고 있다가 뤼팽이 지나가면 잡으려고 한다.

그러나 뤼팽은 눈치가 빠르기 때문에 홈즈가 숨어있는 도시를 거치지 않고 항구로 갈 수 있으면 돌아서 가기 때문에 홈즈는 뤼팽이 반드시 지나갈 수밖에 없는 장소에서 뤼팽을 기다려야 한다.

홈즈가 혼자서 뤼팽을 잡을 수 있으면 좋겠지만 만약 불가능한 경우 홈즈는 친구 왓슨을 불러 두 도시에서 뤼팽을 기다리려고 한다.

만약 홈즈와 왓슨이 숨어 있는 두 도시를 뤼팽이 거치지 않고서는 항구로 갈 수 없으면 홈즈는 뤼팽을 잡을 수 있고 만약 그렇지 않다면 홈즈는 뤼팽을 잡을 수 없다.

그리고 만약 홈즈 혼자서도 뤼팽을 잡을 수 있다면 홈즈는 왓슨을 부르지 않는다. 홈즈가 뤼팽을 잡을 수 있도록 도와주자.

Input

첫 번째 줄에 도시의 수 n 과 간선의 개수 m 이 입력된다.
(3 <= n <= 5000 , 2 <= m <= 10000)

두 번째 줄부터 m+1번째 줄까지 이동이 가능한 두 정점의 번호 x,y가 주어진다.
(1 <= x, y <= n) (x에서 y로 이동이 가능하고 y에서 x로도 이동이 가능하다.)

(뤼팽의 아지트는 1번이고 항구는 n번이다.)
(모든 도시에서 항구로 가는 길이 있음이 보장된다.)

Output

만약 홈즈 혼자서도 뤼팽을 잡을 수 있다면 "Holmes win!"을 출력하고 홈즈가 잠복해야 하는 도시의 번호를 출력한다. 여러 개인 경우 오름차순으로 모두 출력한다.

홈즈가 왓슨을 불러서 뤼팽을 잡을 수 있다면 "Holmes and Watson win!"을 출력하고 홈즈와 왓슨이 잠복해야 하는 도시들의 번호를 출력한다. 여러 쌍인 경우 오름차순으로 모든 쌍을 출력한다.

만약 홈즈와 왓슨이 뤼팽을 잡을 수 없다면 "Lupin win!"을 출력한다.

IO Example

입력 1
5 5
1 2
1 3
2 3
3 4
4 5

출력 1
Holmes win!
3
4

입력 2
7 10
1 5
2 3
3 4
2 1
5 2
3 7
6 7
2 4
4 1
5 6

출력 2
Holmes and Watson win!
3 5
3 6

입력 3
5 6
1 2
1 3
1 4
2 5
3 5
4 5

출력 3
Lupin win!

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