빙고 동시 승리

빙고는 여러 명의 참가자가 즐기는 운 게임이다. 참가자마다 5×5 격자에 숫자가 적힌 빙고 카드를 하나씩 가지고 있다. 각 숫자는 한 카드 안에서 최대 한 번만 등장한다. 사회자가 무작위로 뽑힌 숫자를 차례로 부르면, 참가자는 자신의 카드에 있는 숫자가 불릴 때마다 그 숫자를 표시한다. 자신의 카드에서 표시된 숫자 다섯 개가 가로, 세로 또는 대각선으로 한 줄을 이루면 그 참가자가 승리한다. 승리한 참가자가 “빙고”를 외치면 게임이 끝난다.

당신은 지역 청소년 단체에서 자원봉사를 하며 아이들을 위해 빙고 게임을 진행해 왔다. 아이들은 빙고를 좋아하지만, 두 명 이상의 아이가 동시에 “빙고”를 외칠 때마다 격렬한 “의견 충돌”이 벌어진다. 당신은 동시 승리가 덜 나오기를 바라며 규칙을 조금 바꾼 빙고를 만들었다. 카드는 25개 칸에 각각 1부터 3 000까지의 숫자가 들어 있는 5×5 격자이고, 어떤 참가자가 한 줄에 숫자 다섯 개를 완성했을 때만 승리로 인정된다. 이 새로운 게임에서는 세로줄이나 대각선으로는 이길 수 없다.

아쉽게도 이 변경으로도 동시 승리와 그 뒤의 다툼은 사라지지 않았다. 다툼을 막기 위해 당신은 카드 집합을 분석해 동시 승리, 즉 두 아이가 동시에 빙고를 외칠 수 있는 경우가 존재하는지 판단하기로 했다. 빙고 카드 여러 장이 주어질 때, 게임이 끝나면서 두 명 이상의 참가자가 동시에 승리하고, 그 승리가 마지막으로 불린 숫자에서 일어나는 것이 가능한 숫자 호출 순서가 있는지 판별하는 프로그램을 작성하라.

예를 들어 다음 두 빙고 카드를 보자.

이 두 카드로 이루어진 집합은 숫자를

40 61 64 10 57 49 11 31 25

순서로 부르면 동시 승리가 일어날 수 있다. 이 순서대로 부르면 숫자 25가 불릴 때 왼쪽 카드는 세 번째 가로줄을, 오른쪽 카드는 네 번째 가로줄을 완성한다.

입력의 첫 줄에는 빙고 카드의 수 n (2 ≤ n ≤ 100)이 주어진다. 그다음 줄부터 n개의 빙고 카드가 주어지며, 각 카드 사이에는 빈 줄이 하나씩 있다.

각 빙고 카드는 다섯 줄로 이루어진다. 각 줄에는 1부터 3 000까지 범위의 정수 다섯 개가 주어진다. 각 빙고 카드에 있는 숫자는 서로 다르다.

어떤 두 카드 사이에도 동시 승리가 일어날 수 없으면 “no ties”를 한 줄에 출력한다. 그렇지 않으면 동시 승리가 일어날 수 있는 카드 쌍 중 카드 번호가 가장 작은 쌍을 출력한다. 카드 번호는 입력에 나온 순서대로 1부터 n까지 붙는다. 동시 승리가 가능한 카드 쌍이 여러 개라면 사전순으로 가장 작은 쌍을 출력한다. 즉 첫 번째 카드 번호가 가장 작은 쌍을, 그런 쌍이 여러 개라면 두 번째 카드 번호가 가장 작은 쌍을 출력한다.