바다에서 건진 달

시간 제한3초메모리 제한1024 MB

요약
각 플레이어가 버림패를 누구에게 넘겨줄 수 있는지 주어질 때, I번 사람부터 시작해 F번 사람이 패산의 마지막 패를 뽑아 이길 수 있는지 판별한다.
난이도

보통10점 중 7점

유형
그래프, 그리디, 시뮬레이션, 구현
정답자
아직 제출이 없습니다

문제

preview

마작이 협동 게임이라는 사실을 아시나요?

해저로월 마작은 NN명이 모여서 하는 협동 게임입니다. 각 사람에는 11부터 NN까지의 번호가 붙어 있습니다.

해저로월 마작은 NN명의 사람이 둥글게 둘러앉아서 플레이합니다. 구체적으로는, 1≤i≤N−11 \le i \le N-1을 만족하는 정수 ii에 대해 ii번 사람의 오른쪽에는 i+1i+1번 사람이 있으며, NN번 사람의 오른쪽에는 11번 사람이 있도록 앉습니다. 이후, 다음과 같이 진행합니다.

  1. 주사위를 굴려 게임을 시작할 사람과 게임을 끝내야 하는 사람을 정합니다.
  2. 게임을 시작하는 사람부터 한 명씩 자신의 차례를 진행합니다.
  3. 승리 또는 패배 조건을 만족할 때까지 게임을 진행합니다.

각 플레이어는 자신의 차례가 오는 경우 다음 진행을 순서대로 따라합니다.

  1. 패산에서 한 장의 패를 뽑아옵니다.
  2. 자신이 가져온 패 또는 자신이 원래 가지고 있던 패 중 한 장의 패를 선택해서 버립니다.
  3. 자신의 오른쪽 사람에게 차례를 넘깁니다.

패산牌山이란 마작패들을 쌓아 놓은 더미를 뜻합니다. 패산의 마지막 패는 특별한 패로, 게임을 끝내야 하는 사람이 이 패를 뽑아오게 된다면 해저로월海底撈月로 게임에 승리합니다. 다른 사람이 이 패를 뽑아오게 된다면 게임에 패배하게 됩니다.

추가로, 플레이어들은 조건에 따라 다른 사람 차례의 2번과 3번 진행 사이에 다른 사람이 방금 버린 패를 가져올 수 있습니다. 구체적으로는, 다음과 같은 상황과 제한이 적용됩니다.

  • 다른 사람이 방금 버린 패를 가져옵니다. 기존의 차례를 무시하고 즉시 자신의 차례를 가집니다.
  • 이는 패산 대신 다른 사람이 버린 더미에서 패를 가져오는 행동으로, 패산에서 패를 뽑아오는 1번 진행을 생략합니다.
  • 패산에 남은 패의 수 역시 변하지 않습니다.
  • 여러 명이 하나의 버림패를 가져갈 수 없습니다. 여러 명이 패를 가져가고 싶어하는 경우 합의에 의해 정할 수 있습니다.
  • 자신의 버림패를 가져갈 수 없습니다.

안타깝게도, 모든 사람이 다른 모든 사람의 버림패를 가져올 수 있는 것은 아닙니다. ii번 사람은 M_iM\_i명의 사람들 L_i,1,…,L_i,M_iL\_{i,1}, \dots, L\_{i,M\_i} 중 한 명이 가져갈 수 있는 패를 적절히 선택하여 버릴 수 있고, 그 외의 사람은 ii번 사람의 버림패를 가져올 수 없습니다.

여러분은 이미 주사위를 굴렸습니다. II번 사람이 게임을 시작할 때, FF번 사람이 패산의 마지막 패를 뽑아와 해저로월로 게임에 승리할 수 있는지를 판별해 주세요.

입력

첫 번째 줄에 해저로월 마작을 플레이하는 사람들의 수 NN과 게임을 시작할 때 패산에 남은 패의 개수 PP가 공백으로 구분되어 주어집니다. (3≤N≤5,000;(3 \le N \le 5\\,000; 1≤P≤109)1 \le P \le 10^{9})

두 번째 줄에 게임을 시작하는 사람의 번호 II와 게임을 끝내야 하는 사람의 번호 FF가 공백으로 구분되어 주어집니다. (1≤I≤N;(1 \le I \le N; 1≤F≤N)1 \le F \le N)

세 번째 줄부터 NN개의 줄에 걸쳐 각 사람의 버림패를 가져갈 수 있는 사람의 정보가 주어집니다.

  • NN개의 줄 중 ii번째 줄에는 1+M_i1+M\_i개의 정수가 공백으로 구분되어 주어집니다.
  • 첫 번째 수는 버림패를 가져갈 가능성이 있는 사람의 수 M_iM\_i입니다. (0≤M_i≤N−1;(0 \le M\_i \le N-1; ∑M_i≤5,000)\sum M\_i \le 5\\,000)
  • 나머지 수는 순서대로 L_i,1,…,L_i,M_iL\_{i,1}, \dots, L\_{i,M\_i}입니다. (1≤L_i,j≤N;(1 \le L\_{i,j} \le N; L_i,j≠i;L\_{i,j} \ne i; j≠k→L_i,j≠L_i,k)j \ne k \rightarrow L\_{i,j} \ne L\_{i,k})

출력

게임에 승리할 수 있으면 Tsumo, 게임에 승리할 수 없으면 Ryuukyoku를 출력합니다.

힌트

지문에서 등장하는 게임은 마작을 새롭게 각색한 게임으로, 실제 마작과는 다를 수 있습니다.

해저로월海底撈月 또는 해저모월海底摸月은 바다 깊은 곳에서 달을 건져올린다는 뜻으로, 마작의 역입니다.

예제2

  1. 예제 1

    입력
    3 2
    1 3
    1 2
    2 3 1
    0
    
    예상 출력
    Tsumo
    
  2. 예제 2

    입력
    5 2
    1 3
    1 4
    2 3 5
    0
    0
    0
    
    예상 출력
    Ryuukyoku