길 잃은 고양이
시간 제한5초메모리 제한512 MB
고양이가 마지막으로 지난 간선만 기억한 채 현재 마을의 표시 종류만 보고 움직일 때, 어느 마을에서 출발해도 0번 마을에 d+B 이내로 도착하도록 간선에 표시를 부여하는 문제다.
문제
Anthony는 JOI City에 사는 개미다. JOI City에는 N개의 마을이 있고, 0부터 N − 1까지 번호가 붙어 있다. Anthony는 마을 0에 산다. M개의 도로가 있고, 0부터 M − 1까지 번호가 붙어 있다. 도로 i (0 ≤ i ≤ M − 1)는 마을 Ui와 마을 Vi를 연결하며, 양방향으로 지날 수 있다. 서로 다른 도로는 서로 다른 두 마을 쌍을 연결한다. 어떤 마을에서든 여러 도로를 지나 다른 모든 마을로 이동할 수 있다.
Catherine은 Anthony의 친구인 고양이다. 그녀는 JOI City를 방문할 계획이지만 도로 정보를 모르고 자주 길을 잃는다. Anthony는 미리 도로에 표식을 남기기로 했다. 표식에는 A가지 종류가 있고, 0부터 A − 1까지 번호가 붙어 있다.
이제 Catherine이 JOI City의 어떤 마을에 도착했다. 그녀는 마을 0이 아닌 마을에 있을 때마다 다음을 한다.
각 표식 종류에 대해, 그녀는 현재 마을에서 나가는 그 종류의 도로 수를 셀 수 있다. 단, 마지막으로 지나온 도로는 제외한다(그런 도로가 있다면).
그 후 지날 도로를 하나 고른다. 단, 마지막으로 지나온 도로를 제외하면, 그녀는 도로를 표식 종류로만 구별할 수 있다. 도로를 적절히 고르면 그녀는 시간을 많이 들이지 않고 마을 0에 도착하고 싶어 한다. 더 정확히는, 처음 있던 마을에서 마을 0까지 이동하는 데 지나야 하는 최소 도로 수가 d일 때, 그녀는 도로를 d + B번 이하로 골라 마을 0에 도착하고 싶어 한다.
도로 정보가 주어질 때, Anthony가 도로에 표식을 남기는 전략을 구현하는 프로그램과 Catherine이 도로를 고르는 전략을 구현하는 프로그램을 작성하시오.
제한
- 2 ≤ N ≤ 20 000.
- 1 ≤ M ≤ 20 000.
- 1 ≤ S ≤ N − 1 (S는 Catherine이 처음 도착한 마을의 번호).
- 0 ≤ Ui < Vi ≤ N − 1 (0 ≤ i ≤ M − 1).
- (Ui, Vi) ≠ (Uj, Vj) (0 ≤ i < j ≤ M − 1).
- 어떤 마을에서든 여러 도로를 지나 다른 모든 마을로 이동할 수 있다.