Abstract Art

Time limit2sMemory limit512 MB

Summary

Given an r by c grid of colored cells, find the fewest cells to whiteout so no two different colors touch, and list the colors that can survive at that minimum.

Level: Medium7 of 10
Topics: Graph, Matrix
Solved: No attempts yet

Problem

Peter painted a peculiar piece of art involving a grid of cells. He is not quite happy with it. Some of the colors in his painting are touching, and he does not like that. He would like to use a dab of whiteout to separate any different colors that are touching.

The painting consists of an $r \times c$ grid of cells. Each cell is painted some color. Two colored cells are touching if they share a border edge. Cells sharing only a corner are not considered touching.

Cells are labelled with lowercase letters to denote colors. Peter can replace some of the cells with '#', which represents whiteout. For example:

aaab aa#b
aabb a#bb
aaab aa#b
cccc ##c#

Peter has separated all of the colors using only 6 dabs of whiteout. To save whiteout, Peter wants to minimize the number of cells he must dab.

Peter may accidentally paint over his favorite color while trying to save the painting. So, while using the minimum number of dabs, he wants to know which colors can be retained in the painting.

For example, the painting

bab
bbb

can be fixed using one dab:

b#b
bbb

It is possible to save the color b with a single dab, but it is not possible to use only a single dab and retain the color a.

Input

Each input consists of a single test case. Note that your program may be run multiple times on different inputs.

The first line contains two space-separated integers $r$ and $c$ ( $1 \le r, c \le 100$ ), where $r$ is the number of rows and $c$ is the number of columns.

Each of the next $r$ lines contains a string of length exactly $c$ . Each string consists only of lowercase letters or the symbol '#', which marks a cell that is already whited out.

Output

Output exactly two lines. The first line contains a single integer, the minimum number of additional cells that must be whited out, not counting cells that are already whited out. The second line contains a string of lowercase letters in increasing alphabetical order. These are the colors that can be retained by whiting out a minimum number of cells.

Hint

In the first example, a can be retained with 2 dabs:

a#
#a

And b can be retained with 2 dabs:

#b
b#

So both a and b can be retained with 2 dabs, just not at the same time.

Examples3

Example 1
Input
```
2 2
ab
ba
```
Expected output
```
2
ab
```
Example 2
Input
```
2 3
aba
aaa
```
Expected output
```
1
a
```
Example 3
Input
```
3 4
#a##
bcde
##f#
```
Expected output
```
2
abef
```