You are given a grid, find the longest path in it. The grid is filled with '#' which means blocked cell and '.' which means an empty cell. A path is a chain of empty cells that each cell is neighbor with the next one. Each cell is a neighbor with cells that share a side with it. A cell cannot appear twice in the path.
Input format
Output format
In the first line, print denoting the length of the path.
In the next lines, print the cells in order.
Constraints
Test generation
At the first, a random number is generated in range (0, 1). Then each cell becomes '#' with probability .
10 .....#.... #..##.###. ..#.#..#.. ###.#.#.## .##.#####. ...#...... #...#..### ..#...#.#. ......#... #####...##
Note that obviously, the printed path is not the longest path that can be found, it's just an example.