First Sudoku Mistake

Sudoku is a puzzle played on a 9 by 9 board with 81 cells. The upper-left cell is written as (1, 1), and the lower-right cell is written as (9, 9).

The rules for filling the board are as follows.

1. Each row and each column must contain every digit from 1 to 9 exactly once.
2. Each 3×3 square separated by thick lines must also contain every digit from 1 to 9 exactly once.

In the first pictured situation, the digits 2 through 9 already appear in the same row, column, or 3×3 square, so the empty cell can only contain 1.

In another 3×3 square, every digit except 3 is already present, so the center empty cell can only contain 3.

By filling the cells one by one, it is possible to complete a board that satisfies all rules. However, a wrong number may make the puzzle impossible to finish, even if the move does not immediately duplicate a digit in its row, column, or 3×3 square.

Consider the following board after 29 cells have been filled.

If the 30th move puts 5 in cell (4, 6), the board still appears to obey the local rules at that moment, but no assignment of the remaining 51 cells can complete the puzzle.

Given the order of 81 moves, determine the first step after which the current board can no longer be extended to a completed valid Sudoku board.

The input has 81 lines. Each line contains the row number, column number, and digit placed at that step, separated by spaces. Every value is an integer from 1 to 9.

Print the number of the first step that makes completion impossible. If no mistake occurs after all steps, print -1.