P16756 [GKS 2020 #C] Stable Wall

Apollo is playing a game involving polyominoes. A polyomino is a shape made by joining together one or more squares edge to edge to form a single connected shape. The game involves combining $N$ polyominoes into a single rectangular shape without any holes. Each polyomino is labeled with a unique character from $A$ to $Z$. Apollo has finished the game and created a rectangular wall containing $R$ rows and $C$ columns. He took a picture and sent it to his friend Selene. Selene likes pictures of walls, but she likes them even more if they are *stable* walls. A wall is stable if it can be created by adding polyominoes one at a time to the wall so that each polyomino is always **supported**. A polyomino is supported if each of its squares is either on the ground, or has another square below it. Apollo would like to check if his wall is stable and if it is, prove that fact to Selene by telling her the order in which he added the polyominoes.

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case begins with a line containing the two integers $R$ and $C$. Then, $R$ lines follow, describing the wall from top to bottom. Each line contains a string of $C$ uppercase characters from $A$ to $Z$, describing that row of the wall.

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is a string of N uppercase characters, describing the order in which he built them. If there is more than one such order, output any of them. If the wall is not stable, output -1 instead.

In sample case #1, note that ZOMA is another possible answer. In sample case #2 and sample case #3, the wall is not stable, so the answer is -1. In sample case #4, the only possible answer is EDCBA. ### Limits $1 \le T \le 100$. $1 \le R \le 30$. $1 \le C \le 30$. No two polyominoes will be labeled with the same letter. The input is guaranteed to be valid according to the rules described in the statement. **Test Set 1** $1 \le N \le 5$. **Test Set 2** $1 \le N \le 26$.