스도쿠의 첫 실수

스도쿠는 9행 9열, 모두 81개의 칸으로 이루어진 퍼즐이다. 왼쪽 위 칸은 (1, 1), 오른쪽 아래 칸은 (9, 9)로 나타낸다.

수를 채우는 규칙은 다음과 같다.

1. 각 행과 각 열에는 1부터 9까지의 숫자가 정확히 한 번씩 나타나야 한다.
2. 굵은 선으로 나뉜 각 3×3 정사각형에도 1부터 9까지의 숫자가 정확히 한 번씩 나타나야 한다.

다음 상황에서는 1을 제외한 2부터 9까지의 숫자가 이미 같은 행, 열, 또는 3×3 정사각형에 있으므로 빈칸에는 1만 들어갈 수 있다.

또 다른 3×3 정사각형에서는 3을 제외한 나머지 숫자가 이미 있으므로 가운데 빈칸에는 3만 들어갈 수 있다.

이처럼 칸을 차례대로 채우면 조건을 만족하는 스도쿠를 완성할 수 있다. 하지만 중간에 잘못된 수를 넣으면, 그 순간에는 행·열·3×3 정사각형 규칙과 직접 충돌하지 않더라도 남은 칸을 끝까지 채울 수 없게 될 수 있다.

아래와 같이 29개의 칸이 채워진 상태를 보자.

여기서 30번째로 (4, 6)에 5를 넣으면 현재 단계에서는 겉으로 규칙을 어기지 않지만, 남은 51개의 칸을 어떤 방법으로 채워도 퍼즐을 완성할 수 없다.

주어진 81번의 입력 순서에서, 각 단계까지의 배치가 완성 가능한 스도쿠 판으로 확장될 수 있는지 판단하여 가장 먼저 완성이 불가능해지는 단계 번호를 구하시오.

81개의 줄이 주어진다. 각 줄에는 해당 단계에서 숫자를 놓을 칸의 행 번호, 열 번호, 그리고 놓을 숫자가 공백으로 구분되어 주어진다. 모든 값은 1 이상 9 이하의 정수이다.

가장 먼저 완성이 불가능해지는 단계 번호를 출력한다. 모든 단계를 지나도 실수가 없다면 -1을 출력한다.