Fantastic Beasts
시간 제한2초메모리 제한512 MB
B마리의 짐승이 각자 고정된 함수 f에 따라 매 단위 시간마다 자기 자신이나 f(i)로 이동할 때, 모든 짐승이 처음으로 같은 동물원에 모이는 시각 T와 그 동물원을 구하거나 불가능을 판정한다.
문제
기이한 생물학자 뉴트 스캐맨더는 이 번성하는 왕국에 사는 환상적인 생물을 연구하기 위해 최근 Nlogonia에 왔다. 그러나 지역을 탐사하기 시작하기도 전에 사고가 계획을 망쳤다. 그의 가방이 열려 마법 물체에서 환상적인 짐승들이 탈출한 것이다.
Nlogonia 주민들은 동물원을 사랑해서 왕국에는 동물원이 많다. 짐승들도 Nlogonia 사람들의 동물원 사랑을 공유하는지, 사고 이후 여러 동물원을 방문하고 있다.
짐승이 탈출해 소란을 일으키는 것은 뉴트에게 새로운 일이 아니었기에, 이전 사건 이후 짐승들에게 추적기를 달아 두었다. 따라서 그는 언제든 각 짐승의 정확한 위치를 알고 있다. 얼마 동안 짐승들의 움직임을 관찰한 그는 독특한 패턴을 발견했다. 짐승이 현재 어떤 동물원에 있으면, 단위 시간 후에는 그 동물원에 머물거나 현재 동물원에 따라 정해지는 다른 동물원으로 이동한다. 다른 동물원으로 이동하는 모든 짐승은 동시에 즉시 이동한다.
이 정보를 바탕으로 뉴트는 어쩌면 생물들을 회수하는 일이 그리 어렵지 않을 수도 있다고 추측했다. 결국 모든 짐승이 같은 시각에 같은 동물원에서 만날 수 있으니, 올바른 장소에서 기다리기만 하면 모든 환상적인 짐승을 한 번에 잡을 수 있다고 생각했다. 지금까지의 정보를 바탕으로, 짐승들을 어디서 언제 기다려야 하는지 알아낼 수 있을까? 가능한 경우가 여러 개라면, 그는 짐승들을 가능한 한 빨리 잡고 싶어 한다.
입력
첫째 줄에 두 정수 B (1 ≤ B ≤ 10)와 Z (1 ≤ Z ≤ 100)가 주어진다. 각각 환상적인 짐승의 수와 동물원의 수다. 동물원은 1부터 Z까지 서로 다른 정수로 식별된다. 다음 B개의 줄 각각은 서로 다른 짐승에 대한 뉴트의 조사 결과를 Z + 1개의 정수 P0, P1, . . . , PZ (1 ≤ Pi ≤ Z for i = 0, 1, . . . , Z)로 나타낸다. 값 P0는 짐승이 처음에 있는 동물원이고, i = 1, 2, . . . , Z에 대해 Pi는 짐승이 현재 동물원 i에 있을 때 단위 시간 후에 있게 될 동물원이다.
출력
모든 짐승이 T 단위 시간 후에 처음으로 동물원 P에서 만나면 두 정수 P와 T를 한 줄에 출력한다. 짐승들이 같은 동물원에 모두 모이는 일이 없다면 문자 “*”(별표)를 출력한다.
입력에서 T는 9,223,372,036,854,775,807 이하이다.