Bojanje

시간 제한1초메모리 제한2048 MB

요약

흰색, 빨강, 파랑으로 칠해진 n×n 격자가 행과 열에 대한 덧칠 순서로 만들어질 수 있는지 판정하고, 가능하면 그 순서를 출력한다.

난이도: 보통10점 중 5점
유형: 시뮬레이션, 그리디, 구현
정답자: 아직 제출이 없습니다

문제

Marin, having become exceptionally skilled in competitive programming, decided to find a new hobby to keep himself entertained while waiting for you to catch up. While you were solving previous problems, Marin discovered a great love for painting.

He took a blank white canvas and two colors, red and blue. He began painting perfectly horizontal and vertical strokes on the canvas, from one edge to the opposite edge. The canvas can be imagined as an $n \cdot n$ grid, where rows and columns are numbered from $1$ to $n$ , and it starts completely white. Each of Marin’s strokes can be imagined as choosing one of the two colors and a row or column, then coloring all the cells in that row/column with the chosen color, regardless of what was previously on the field. Marin will make a finite number of strokes and complete his painting.

However, his friend Stjepan found a painting that resembles Marin’s but is unsure if it is really his. The painting he found can again be imagined as an $n \times n$ grid where each cell is white, blue, or red. The painting is possibly Marin’s if there exists a sequence of strokes on a blank canvas, as described above, that produces an image identical to the one found. Stjepan has asked you to help him determine whether the painting might be Marin’s and, if so, to find a sequence of strokes that produces the found painting.

입력

The first line contains a positive integer $n$ ( $1 ≤ n ≤ 2000$ ).

In the next $n$ lines, there are $n$ integers $a\_{i,j}$ ( $0 ≤ a\_{i,j} ≤ 2$ ), where each represents the color in the $i$ -th row and $j$ -th column ( $0$ if white, $1$ if red, and $2$ if blue).

출력

If the painting is possibly Marin’s, then in the first line, print the number of strokes $K$ ( $0 ≤ K ≤ 4000$ ). In the next $K$ lines, you should print three integers. The first will indicate whether the $i$ -th stroke was on a row or a column ( $1$ for a row, $2$ for a column). The second number will indicate the index of the row or column where the stroke is performed, and the third number will indicate the color in the same way as described in the Input section.

If the painting is certainly not Marin’s, print "-1" (without quotes) in the first and only line.

예제3

예제 1
입력
```
3
0 0 1
1 1 1
0 0 1
```
예상 출력
```
2
2 3 1
1 2 1
```
예제 2
입력
```
3
1 1 2
2 1 1
2 1 1
```
예상 출력
```
-1
```

예제 3

입력

예상 출력