실행 시간 제한 | 메모리 제한 |
---|---|
4 초 | 512 MB |
사냥꾼들에게 포위된 돼지가 외딴 농장에 숨어 있습니다. 농장은 개의 헛간()과 헛간 사이를 이어주는 개의 양방향 터널로 구성되어 있어, 모든 헛간 쌍 사이의 경로는 고유합니다. 터널이 한 개만 있는 모든 헛간은 출구입니다. 아침이 오면, 돼지는 어느 헛간에서든지 나타나서 출구를 향해 탈출을 시도할 것입니다.
하지만 돼지가 어느 헛간에서든지 모습을 드러내는 순간, 사냥꾼들은 돼지의 위치를 정확히 파악할 수 있습니다. 동시에 몇몇 사냥꾼들은 다른 출구 헛간에서 출발해서 돼지를 잡으려고 시도할 것입니다. 사냥꾼들은 돼지와 같은 속도로 움직입니다(즉, 각 시간 단계에서 각 사냥꾼은 한 헛간에서 인접한 헛간으로 이동 할 수 있습니다). 사냥꾼들은 돼지가 어디 있는지 항상 알고 있으며, 돼지는 사냥꾼들이 어디 있는지 항상 알고 있습니다. 만약 사냥꾼이 돼지와 같은 헛간에 있거나 돼지와 같은 터널을 건너는 경우에 사냥꾼은 돼지를 잡습니다. 반대로, 돼지는 사냥꾼들이 돼지를 잡기 전에 출구 헛간에 도착하면 탈출합니다.
돼지는 어느 헛간에서 나타나야 할지 확신하지 못하고 있습니다. 개의 헛간 중 각각에 대해, 돼지가 그곳에서 나타났을 때 사냥꾼들이 최적으로 출구 헛간에 배치되어 있다고 가정했을 때, 돼지를 잡기 위해 필요한 사냥꾼의 최소 수를 베시가 파악하도록 도와주세요.
입력의 첫 번째 줄에는 이 포함되어 있습니다. 다음 줄에는 각각 두 개의 정수가 포함되어 있으며, 이는 의 범위 내에 있어 두 헛간 사이의 터널을 설명합니다.
개의 줄을 출력해 주세요. 출력의 번째 줄은 돼지가 번째 헛간에서 나타났을 경우 돼지를 잡기 위해 필요한 사냥꾼의 최소 수를 알려줍니다.
7 1 2 1 3 3 4 3 5 4 6 5 7
3 1 3 3 3 1 1
출처: USACO 2018 January Contest, Platinum Problem 2. Cow at Large