[COCI2018-2019#3] Sajam

题目背景

Milo 组织了一场圣诞游园会。结束后，他想通过 LEET 来实现熄灯。

题目描述

每个区域都由 NN 行组成，其中每行有 \(N\) 个摊位。现有 \(3\) 种操作方式改变发光状态指将原来发光的灯改为熄灭，反之亦然）：

1. LEET 将选定一整行，并自动将这行所有的灯改变发光状态。
2. LEET 将选定一整列，并自动将这列所有的灯改变发光状态。
3. Milo 将选定一个摊位，并手动将该摊位的灯改变发光状态。 是否有方案使得 Milo 能在最多进行 \(K\) 次操作 \(3\) 的情况下，将所有灯全部熄灭？

输入格式

第一行输入整数 \(N,K\)。

接下来的 \(N\) 行，每行有 \(N\) 个字符 x 或 o，表示圣诞游园会对应摊位灯的发光状态。其中 x 指熄灭，o 指发光。

输出格式

如果有符合题意的方案，则输出 DA，否则输出 NE。

样例 #1

样例输入 #1

2 0
ox
ox

样例输出 #1

DA

样例 #2

样例输入 #2

3 1
ooo
xoo
oox

样例输出 #2

NE

样例 #3

样例输入 #3

4 2
oxxo
xxox
oxoo
oxxo

样例输出 #3

DA

提示

样例 3 解释

一种符合题意的方案：

• 执行操作 2，选定第 1 列。
• 执行操作 3，选定 (2,2)。
• 执行操作 1，选定第 2 行。
• 执行操作 2，选定第 4 列。
• 执行操作 3，选定 (3,3)。