Alice's Teleportation Path

Alice is trapped in an \(n \times n\) grid where each cell is either traversable (denoted by '0') or blocked (denoted by '1'). She starts at the top-left cell (1,1) and her destination is the bottom-right cell (n,n).

Alice can move to any adjacent cell (up, down, left, or right) if that cell is traversable. In addition, she has up to \(k\) teleportation gadgets. Each gadget allows her to instantly jump from her current position to any other traversable cell in the grid.

Your task is to determine whether Alice can reach the destination. If so, report the minimum number of teleportation gadgets she needs to use during her journey. Otherwise, output "NO".

inputFormat

The first line contains two integers (n) and (k), where (n) is the size of the grid and (k) is the number of available teleportation gadgets. The following (n) lines each contain a string of (n) characters, which can be either '0' (traversable) or '1' (blocked).

outputFormat

If Alice can reach the bottom-right cell, output "YES " followed by the minimum number of teleportation gadgets used. If it is impossible for her to reach the destination, output "NO".## sample

5 1
00000
01110
00000
01110
00000

YES 1