레이팅 미적용농부 존(Farmer John)이 베시(Bessie)와 소들을 유람선 여행에 데려간다! 이들은 1..N으로 번호가 붙은 N개 (1 <= N <= 1,000)의 항구가 있는 강의 네트워크를 항해하며, 베시는 항구 1에서 출발한다. 각 항구에는 다른 항구로 직접 이어지는 나가는 강이 정확히 두 개 있으며, 강은 한 방향으로만 항해할 수 있다.
각 항구에서 여행 가이드들은 다음에 항해할 강으로 "왼쪽" 강 또는 "오른쪽" 강을 고르는데, 같은 선택들을 계속 반복한다. 더 구체적으로, 여행 가이드들은 각각 "왼쪽" 또는 "오른쪽"인 M개 (1 <= M <= 500)의 방향으로 이루어진 짧은 수열을 정해 놓고, 그것을 K번 (1 <= K <= 1,000,000,000) 반복했다. 베시는 자기가 계속 제자리를 맴돌고 있다고 생각한다. 베시가 최종적으로 어디에 도착하는지 알아내는 것을 도와주자!
첫째 줄: 공백으로 구분된 세 정수 N, M, K.
둘째 줄부터 N+1번째 줄까지: i+1번째 줄에 공백으로 구분된 두 정수가 주어지며, 각각 항구 i의 왼쪽 강과 오른쪽 강이 이어지는 항구의 번호를 나타낸다.
N+2번째 줄: 'L' 또는 'R'인 M개의 문자가 공백으로 구분되어 주어진다.
베시의 유람선 여행이 끝나는 항구의 번호를 나타내는 정수 하나.
cruise.in · 출력을 쓸 파일 cruise.out4 3 3
2 4
3 1
4 2
1 3
L L R4Output details: The sequence taken is LLRLLRLLR; Bessie ends at port 4.
riseoj 작성
출처 올림피아드 > USACO > 2012-2013 > US Open > Silver