牛牛VS牛妹

题号：NC21669
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld

题目描述

给你一个网格，有些点被#覆盖了不能再走，其他点是空地，现在牛牛和牛妹轮流开始将空地变成#
如果当前轮到的人操作之后左上角到右下角不存在通路了，当前操作的人就输了
通路只能是从左上角到右下角往右或者往下走的路径
牛牛先开始操作，如果双方都是绝顶聪明，输出最后谁赢

保证一开始给你的网格是存在一条左上角到右下角的通路的，当然，左上角与右下角都是空地。

输入描述:

第一行输入两个整数n,m(2≤ n,m ≤ 20)

接下来n行每行输入m个字符用来描述网格

输出描述:

输出赢的人的名字，"niuniu" 或者 "niumei"

示例1

输入

复制

2 2
..
..

输出

复制

niuniu

示例2

输入

复制

4 3
...
.#.
.#.
...

输出

复制

niumei

示例3

输入

复制

3 3
.##
..#
#..

输出

复制

niumei

示例4

输入

复制

4 4
....
...#
#...
....

输出

复制

niuniu

备注:

子任务一30分：max(n,m)<=5

子任务二30分：max(n,m)<=10

子任务三40分：max(n,m)<=20