|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||512 MB||0||0||0||0.000%|
It is suspected, that the military factory on the outskirts of the town is connected with a series of recent crimes. Public Safety Bureau sent inspector Akane to find out if that was the case.
Akane has a rectangular map of the factory, which is a table of size $m \times n$. Each cell of the map is either empty, or contains one of the factory's workshops. Of course, all workshops are cell-connected. That is, it's possible to get from any workshop to any other workshop through several intermediate workshops, going only between workshops sharing a side. It's also guaranteed, that the factory doesn't enclose any area that doesn't belong to the factory. That is, it's possible to get from any non-workshop cell to the border of the map, going only through non-workshop cells sharing a side.
Akane believes, that in case there are some clues to find, it's more likely that they are located in the corner of some workshop, rather than in it's center. For the above-mentioned map consider all grid nodes that are at the corner of at least one workshop. Akane calls such nodes important. It's easy to see, that the number of important nodes is at most $(m + 1) \cdot (n + 1)$. Akane also found out, that there are corridors on the border of each workshop cell connecting adjacent grid nodes at the corners of this cell.
Akane wants to traverse all the important nodes and to do it in a most efficient way. More precisely, Akane wants to make a route going through the nodes of the grid, such that:
Please help Akane find any valid route or determine, that it's impossible. Please note, that it's not required to minimize the length of the route.
The first line contains integers $m$ and $n$ ($1 \le m, n \le 20$) --- the size of the map with the factory.
The following $m$ lines contain $n$ characters each and describe the factory's map. The character "
*" denotes the workshop, while "
." denotes an empty cell.
In case it's impossible to traverse the factory, print "
Otherwise print "
Yes" and then the number of corridors Akane will go through.
Then print the route itself, one grid node per line. Let's number all horizontal grid lines from $0$ to $m$ upside down and number all vertical grid lines from $0$ to $n$ from left to right. Each grid node is described with two integers $r_i$ and $c_i$ ($0 \le r_i \le m$, $0 \le c_i \le n$) --- the row number and the column number.
3 3 *** *** .**
Yes 16 0 0 0 1 1 1 1 2 1 3 0 3 0 2 1 2 2 2 2 3 3 3 3 2 3 1 2 1 2 0 1 0
1 4 ****
Yes 10 0 0 0 1 0 2 0 3 0 4 1 4 1 3 1 2 1 1 1 0
2 2 ** **
Akane's route in the first example is as follows: