Background

The original time limit is 5 s, and it is set to 1 s here. Tests show that the correct algorithm can pass normally.

Milo organized a Christmas fair. After it ended, he wanted to use LEET to turn off the lights.

Problem Description

Each area consists of $N$ rows, and each row has $N$ stalls. There are $3$ types of operations to change the lighting state (changing a lit lamp to unlit, and vice versa):

1. LEET selects an entire row and automatically toggles the lighting state of all lamps in that row.
2. LEET selects an entire column and automatically toggles the lighting state of all lamps in that column.
3. Milo selects one stall and manually toggles the lighting state of the lamp at that stall.

Is there a way for Milo to turn off all lamps, using operation 3 at most $K$ times?

Input Format

The first line contains integers $N, K$.

The next $N$ lines each contain $N$ characters x or o, representing the lighting state of the lamps at the corresponding stalls in the Christmas fair. Here, x means unlit, and o means lit.

Output Format

If there is a plan that satisfies the requirement, output DA; otherwise output NE.

2 0
ox
ox

DA

3 1
ooo
xoo
oox

NE

4 2
oxxo
xxox
oxoo
oxxo

DA

Hint

Explanation for Sample 3

One feasible plan is:

• Perform operation $2$, selecting column $1$.
• Perform operation $3$, selecting $(2,2)$.
• Perform operation $1$, selecting row $2$.
• Perform operation $2$, selecting column $4$.
• Perform operation $3$, selecting $(3,3)$.

Constraints

For $15$ points, $K = 0$.

For another $15$ points, $N \le 100$.

For another $30$ points, $K \lt \dfrac{N}{2}$.

For $100\%$ of the testdata, $1 \le N \le 1000$, $0 \le K \le N$.

Notes

The scoring of this problem follows the original COCI settings, with a full score of $90$. Only $18$ test points with different difficulties are selected for evaluation here.

Translated from COCI2018-2019 CONTEST #3 T3 Sajam.

Translated by ChatGPT 5