Maximum Chess Pieces Removal on a Grid

Little S is given a \(n\times m\) chessboard. Initially, every cell contains a chess piece. In each move, Little S may remove a chess piece from a cell \(v\) if the number of pieces already removed from the four cells adjacent to \(v\) (up, down, left, right) is at most 1. The task is to determine the maximum number of pieces that can be removed and to output a valid removal sequence achieving this maximum.

The answer is defined as follows:

• If either \(n=1\) or \(m=1\), the board is a line and no cycles occur; in this case the answer is \(n\times m\) (i.e. all pieces may be removed).
• If \(n\ge2\) and \(m\ge2\), the board contains a cycle (a 2×2 block) so it is impossible to remove every piece. In fact, one can prove that the maximum number of removable pieces is \(n\times m-1\).

A valid removal sequence is an ordering of cells to remove such that when a piece is removed, among its 4–neighbor cells, at most one has already been removed. In the output we list the moves in order. Each move is given by the row and column of the removed piece (1-indexed). Note that if \(n\ge2\) and \(m\ge2\) you must leave exactly one piece on the board.

Note: It can be shown that if there exists a valid removal order that removes a set \(S\) of cells, then for every cell \(v\) in \(S\) the number of its neighbors that appear earlier in the order is at most 1.

Your submission must output an answer that can pass all the test cases described.

inputFormat

The input consists of a single line containing two space-separated integers \(n\) and \(m\) \((1\le n,m\le 10)\). (Note: the upper bound is small to allow a backtracking solution.)

outputFormat

On the first line, output the maximum number of pieces that can be removed. Then, output that many lines. Each of these lines must contain two space‐separated integers representing the 1-indexed row and column of the piece removed in that move, in order.

sample

2 2

3
1 2
1 1
2 1