Abraham's Great Escape

Let

$m=n^2-k$

be the number of cells from which Abraham should not escape.

This is way easier than thinking about the $k$ escaping cells directly.

Key observation

Every cell has exactly one outgoing arrow. So if Abraham starts from a cell and never escapes, his path stays inside a finite grid forever. That means some cell must repeat, so the path eventually enters a directed cycle.

But arrows move exactly one cell up/down/left/right. There are no self-loops. So a directed cycle needs at least $2$ cells.

Therefore, having exactly one non-escaping cell is impossible.

So if

$m=1,$

we print NO.

Equivalently, the only impossible case is

$k=n^2-1.$

One trapped cell by itself is just sad. It has nowhere legal to point without eventually leaving its one-cell prison.

Now construct everything else

If $m=0$, all cells should escape. Easy: fill the whole grid with U. Every path moves upward until it exits.

Now assume $m \ge 2$.

We will choose exactly $m$ non-escaping cells in the bottom-left part of the grid:

• first fill the bottom row from left to right,
• then the row above it from left to right,
• and so on.

In coordinates, for IDs $0,1,\dots,m-1$, choose

$r=n-1-\left\lfloor\frac{id}{n}\right\rfloor, \qquad c=id \bmod n.$

This selected region is nice because it is downward closed: if a selected cell is not on the bottom row, then the cell directly below it is also selected.

Now assign arrows:

• The bottom-left cell points right: R.
• The cell immediately to its right points left: L.

These two form a $2$-cycle:

RL

That is our trap.

For every other selected cell:

• if it is on the bottom row, point it left with L, so it walks toward the trap;
• otherwise, point it down with D, so it eventually reaches the bottom row.

All unselected cells stay U.

Why trapped cells do not escape

Take any selected cell.

If it is above the bottom row, it points down to another selected cell. Repeating this eventually reaches the bottom row.

On the bottom row:

• column $0$ points to column $1$,
• column $1$ points back to column $0$,
• every later selected column points left until it reaches that cycle.

So every selected cell eventually enters the bottom-left $2$-cycle. None escape.

Why unselected cells do escape

Every unselected cell has arrow U.

Because the selected region is bottom-left/downward closed, if a cell is unselected, then the cell above it is also unselected whenever that cell exists. So following U from an unselected cell never enters the trapped region. It just keeps going upward until it leaves the grid.

So exactly the selected $m$ cells are non-escaping, and exactly

$n^2-m=k$

cells escape.

Complexity

We fill an $n \times n$ grid once, so each test case is $O(n^2)$. The total input size already guarantees this is fine.