#P18342. [OMI 2025]Mimo and Yuyu

[OMI 2025]Mimo and Yuyu

题目描述

米莫(Mimo)和悠悠(Yuyu)刚拼完一幅 1000 块的拼图,便发明了一个新游戏。

游戏在一个 n×mn\times m 的矩形棋盘上进行,有无限供应的 María 饼干。棋盘的行从上到下编号为 1,2,…,n1,2,\ldots,n,列从左到右编号为 1,2,…,m1,2,\ldots,m。格子 (x,y)(x,y) 表示第 xx 行、第 yy 列。同一个格子可以同时放置任意多块饼干。

初始共有 kk 块饼干,第 ii 块放在 (xi,yi)(x_i,y_i)。

两人轮流操作,米莫先手。每次操作,当前玩家需要选择一块饼干 gg,同时指定一条由互不相同的格子构成的路径

(a1,b1),(a2,b2),…,(ap,bp),(a_1,b_1),(a_2,b_2),\ldots,(a_p,b_p),

其中必须满足:

  1. p≥2p\ge 2;
  2. 选中的饼干 gg 位于起点 (a1,b1)(a_1,b_1);
  3. 相邻路径格子在棋盘上具有公共边,即对所有 1≤i<p1\le i<p,∣ai+1−ai∣+∣bi+1−bi∣=1;|a_{i+1}-a_i|+|b_{i+1}-b_i|=1;
  4. 途经格子的列编号不增加:b1≥b2≥⋯≥bp;b_1\ge b_2\ge\cdots\ge b_p;
  5. 路径终点位于第一列:bp=1b_p=1;
  6. 第一步必须向左移动一格:b2=b1−1b_2=b_1-1。因此路径中只有起点属于第 b1b_1 列。

执行操作时,玩家吃掉起点的那块饼干 gg,然后在路径经过的每一个其他格子

(a2,b2),(a3,b3),…,(ap,bp)(a_2,b_2),(a_3,b_3),\ldots,(a_p,b_p)

各放置一块新饼干,结束本回合。路径格子在本次操作中不得重复,但已经存在的饼干不会妨碍路径经过,新饼干可以与已有饼干重叠。

轮到某玩家时,如果不存在合法操作,则该玩家失败。双方都采用最优策略,请判断先手米莫是否能够获胜。

输入格式

第一行一个整数 tt,表示测试用例数量。

对于每组测试用例:

  • 第一行三个整数 n,m,kn,m,k,依次表示棋盘行数、列数、初始饼干数量。
  • 接下来 kk 行,每行两个整数 xi,yix_i,y_i,表示第 ii 块饼干的位置。

同一组内允许多个饼干的位置完全相同。

输出格式

每组测试用例输出一行:

  • 若米莫(先手)必胜,输出 Mimo;
  • 若悠悠(后手)必胜,输出 Yuyu。

大小写必须完全一致。

样例 1

输入:

1
2 3 2
2 2
1 3

输出:

Mimo

样例 2

输入:

2
6 4 3
2 3
4 2
6 4
6 4 11
6 3
5 3
4 3
3 3
2 3
2 3
2 2
3 2
4 2
4 2
4 1

输出:

Mimo
Yuyu

数据范围

令 SkS_k 为同一个输入文件内所有测试用例的 kk 之和。

$$\begin{aligned} 1 &\le t\le 10^4,\\ 1 &\le n,m,k\le 2\times10^5,\\ S_k &\le 2\times10^5,\\ 1 &\le x_i\le n,\\ 1 &\le y_i\le m. \end{aligned}$$

子任务

子任务 分值 额外条件
1 12 n=2, m=3, k≤3n=2,\ m=3,\ k\le3
2 m≥2m\ge2,所有 yi=2y_i=2
3 k=1k=1
4 k=2k=2
5 n≥2n\ge2,所有饼干在同一列
6 25 n=1n=1
7 15 n≥2n\ge2