농부 창호는 소들이 비에 젖는 걸 너무나도 싫어해서, 농장에 언제 비가 오는지 알려주는 사이렌을 설치했다.

소들은 비가 오기 전에 대피 작전을 세워서 한 마리의 소도 빠짐 없이 모두 헛간 안으로 대피하려고 한다.

하지만 불행하게도 일기예보가 자주 틀려서 난감한 일이 발생되곤 한다.

비가 오지도 않는데 사이렌을 울리는 일을 최대한 줄이고, 소들이 대피할 시간을 미리 충분히 파악하여 가능한 한 사이렌을 늦게 울리려고 한다.

농장에는 N개의 목초지가 있고 목초지에는 소들이 대피할 수 있는 헛간이 세워진 곳도 있다.

헛간은 크기가 제한되어 있어서 한 헛간에 모든 소들이 들어가지 못할 수도 있으며 목초지에서 헛간으로 들어가거나 나오는 데에는 시간이 걸리지 않는다.

목초지 사이에는 소들이 이동할 수 있는 M개의 길이 있고 그 길들은 매우 넓어서 아무리 많은 소들도 한꺼번에 마음껏 양방향으로 이동할 수 있다.

창호를 위해 모든 소들이 헛간으로 대피할 때까지 걸리는 최소 시간을 구하는 프로그램을 작성해 주자.

비 피하기 (takeshelter) timer 1s memory 128MB

비 피하기 (takeshelter) 1s 128MB