You are playing a computer game in which your goal is to flood the whole world.
The world is an r × c rectangle divided into unit square cells. Currently, all cells are dry. The game has two separate phases:
You are given the dimensions of the world. Flood the entire world using as few clicks as possible.
The first line of the input file contains an integer t specifying the number of test cases. Each test case is preceded by a blank line.
Each test case consists of a single line with two positive integers r and c: the dimensions of the world. The individual cells of the world have coordinates ranging from (0, 0) to (r − 1, c − 1).
You may assume that t = 100 and that 1 ≤ r, c ≤ 100.
In the easy subproblem A1 you may also assume that r = c (i.e., the world is a square).
For each test case output a block of lines. The first line of the block should contain the number x of clicks you should make. Each of the following x lines should contain the coordinates of a cell you should click. There are usually multiple optimal solutions. We will accept any of them.
Do not submit any programs. Your task is to produce and submit the correct output files
a2.out for the provided input files
2 2 2 3 4
2 0 1 1 0 4 0 0 0 2 2 2 2 3
The second sample output is illustrated below, with ‘W’ denoting a water cell and ‘.’ denoting a dry cell. On the left is the state of the world just after you made the four clicks. Progressing towards the right you see how the water spreads until it floods the entire world.
W.W. WWW. WWW. WWWW WWWW .... -> ..W. -> .WWW -> WWWW -> WWWW ..WW ..WW ..WW .WWW WWWW