사기꾼

마르티나스(Martynas)는 N명의 친구들과 함께 비디오 게임 사기꾼을 한다. 게임의 무대는 M개의 방으로 이루어진 우주선이다. 게임이 시작되면 각 플레이어에게 비밀리에 역할이 주어진다. 정확히 한 명이 사기꾼이고, 나머지는 모두 승무원이다.

승무원의 목표는 우주선의 임무를 계속 수행하면서 사기꾼이 누구인지 밝혀내는 것이고, 사기꾼의 목표는 우주선에 홀로 남는 것이다.

사기꾼은 여러 턴에 걸쳐 진행된다. 한 턴 동안 다음이 일어난다.

1. 살아남은 모든 플레이어는 그 턴에 자신에게 배정된 방으로 이동한다.
2. 승무원들은 배정된 정비 임무를 수행한다.
3. 사기꾼은 자신과 같은 방에 있는 플레이어 한 명을 희생자로 골라 우주선에서 제거한다. 사기꾼에게는 항상 자신이 혼자 있지 않은 방이 배정된다.
4. 사기꾼과 같은 방에 있던 모든 플레이어는 그가 누군가를 제거하는 장면을 목격한다. 따라서 그들은 누가 사기꾼인지 알게 되며, 남은 게임 내내 이를 기억한다.
5. 턴이 끝나면 우주선에 남아 있는 모든 플레이어가 방에서 나와 빨간 버튼 또는 노란 버튼을 눌러 투표한다. 사기꾼이 누구인지 아는 플레이어는 빨간 버튼을, 모르는 플레이어는 노란 버튼을 누른다. 사기꾼인 마르티나스도 투표하며, 정체를 들키지 않기 위해 항상 노란 버튼을 누른다.
6. 노란 버튼보다 빨간 버튼이 더 많이 눌리면 사기꾼의 정체가 드러난다. 그는 패배하고 게임이 중단된다.

N명의 승무원이 모두 제거되고 사기꾼(즉 (N+1)번째 플레이어)만 게임에 남으면 사기꾼이 승리한다.

마르티나스는 곧 있을 게임에서 자신이 사기꾼이 된다는 것과, 각 턴마다 어떤 플레이어가 어느 방으로 가는지를 미리 알게 되었다. 그는 이 정보를 분석해 각 턴에 누구를 제거할지 미리 계획했다. i번째 턴에는 플레이어 $p_i$를 제거한다. 사기꾼은 자신과 같은 방에 있는 사람만 제거할 수 있으므로, i번째 턴에 사기꾼은 그 턴에 플레이어 $p_i$가 배정된 방에 있게 된다.

마르티나스가 게임에서 승리할지, 승리하지 못한다면 몇 번째 턴에 정체가 드러날지 판단하라.

첫째 줄에는 두 양의 정수가 주어진다. 사기꾼이 아닌 플레이어의 수 $N$과 방의 수 $M$이다.

둘째 줄에는 서로 다른 $N$개의 양의 정수 $p_i$가 주어진다. 이는 마르티나스가 i번째 턴에 제거할 플레이어의 번호이다.

이어지는 $N$개의 줄에는 각각 $N$개의 양의 정수가 주어진다. 그중 i번째 줄의 j번째 수는 $k_{i,j}$로, i번째 턴에 (그 전에 제거되지 않았다면) 플레이어 j가 이동할 방의 번호이다.

하나의 양의 정수를 출력한다. 마르티나스가 게임에서 승리하면 $N$을, 그렇지 않으면 마르티나스가 게임에서 제거되는 턴의 번호를 출력한다.

• $1 \le N, M \le 1000$
• $1 \le k_{i,j} \le M$
• $1 \le p_i \le N$이며, 모든 $p_i$는 서로 다르다.