Escape

Prisoners are trying to escape from a square prison through one of its exits. The prison is an N x N grid. A prisoner may move only up, down, left, or right, and cannot pass through walls.

One guard can stand on one empty corridor cell and stop a prisoner who tries to pass through that exact cell. In the dark, a guard cannot notice a prisoner passing through an adjacent cell, so each guard blocks only the cell they occupy. Guards cannot be placed on prisoner cells or exit cells.

Determine whether at most K guards can prevent every prisoner from reaching any exit. If it is possible, find the minimum number of guards required.

The first line contains the size N of the square prison and the number K of available guards. The next N lines describe the prison.

• +: wall
• .: empty corridor
• X: position of a prisoner trying to escape
• O: exit to the outside

There is at least one exit.

If every escape route can be blocked with at most K guards, print Yes on the first line. Then print the minimum required number of guards on the second line. If it is impossible, print only No on the first line.

• 1 ≤ N ≤ 100
• 0 ≤ K ≤ 1,000