Colored Domino Tilings and Cuts

All submissions for this problem are available.
Consider rectangular grid that composed of N rows and M columns. Colored domino tiling of the grid is some way to put lowercase English letter in each cell of the grid provided that each cell has exactly one neighbor with the same letter as in this cell. Two cells of the grid are neighbors if they share a common side. Each letter represents some color. Cut of colored domino tiling is vertical or horizontal line that divides the grid in two colored domino tilings. In other words this line should not pass between two adjacent cells with the same color.
For given N and M you should find the colored domino tiling that has the minimal possible number of cuts. If there are several solutions you should find among them the tiling that uses the minimal possible number of colors in it. If your tiling requires K colors then use first K lowercase letters of English alphabet as colors. If there are still several solutions then find any such tiling.
Input
The first line contains a positive integer T, the number of test cases. In the following lines, T test cases follow. Every test case is a single line that contains two space separated positive integers, N and M, the sizes of the grid.
Output
For each test case output in the first line the word "IMPOSSIBLE" without quotes if there are no tilings of the grid with N rows and M columns. Otherwise output in the first line two space separated integers, the minimal number of cuts and minimal number of colors in required tiling and then in the next N lines output the tiling itself. Each of these N lines must be composed of exactly M lowercase English letters.
Constraints
1 <= T <= 3000
1 <= N, M <= 500
sum of N*M in the file <= 2,000,000
Sample input
5 1 1 2 2 2 3 4 3 5 5
Sample output
IMPOSSIBLE 1 2 ab ab 1 3 aab ccb 1 3 aab ccb baa bcc IMPOSSIBLE
Author:  anton_lunyov 
Tester:  chmel_tolstiy 
Editorial  http://discuss.codechef.com/problems/DOMNOCUT 
Tags  anton_lunyov hard nov11 
Date Added:  23072011 
Time Limit:  4 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.4, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions