← 返回题目列表

Codeforces · 335/C

C. 更多回收

中文机器翻译题面 查看原题

在一片遥远的土地上,一条河边有两座城市。有一天,这些城市认为他们的空间太小,想将一些河流区域开垦为土地。

河流区域可以用 r 行和两列的网格来表示 - 每个单元格代表一个矩形区域。行从上到下编号为 1 到 r,列编号为 1 和 2。

最初,所有单元格都被河流占据。该计划是将其中一些小区一一变成土地,城市轮流选择一个小区进行开垦,一直持续到没有更多的小区可以开垦为止。

然而,这条河也被用作主要贸易路线。城市需要确保船只仍然能够从河流的一端航行到另一端。更正式地说,如果单元格(r,c)已被回收,则不允许回收任何单元格(r-1,3-c)、(r,3-c)或(r+1,3-c)。

城市关系并不友好,每个城市都希望成为最后一个回收单元的城市(他们不关心回收多少单元,只关心谁最后回收单元)。这些城市已经回收了n个单元格。你的工作是确定哪个城市将是最后一个收回单元格的城市,假设两个城市都从当前时刻选择了最佳单元格。

输入

第一行由两个整数 r 和 n (1 ≤ r ≤ 100, 0 ≤ n ≤ r) 组成。接下来是 n 行,描述已经被回收的单元格。每行由两个整数组成:ri 和 ci(1 ≤ ri ≤ r,1 ≤ ci ≤ 2),表示位于 ri 行和 ci 列的单元格。描述单元的所有行都将是不同的,并且回收的单元不会违反上述约束。

输出

如果轮到选择小区的城市能够保证他们将是最后一个选择小区的城市,则输出“WIN”。否则打印“LOSE”。

示例

输入 #1

3 1
1 1

输出 #1

WIN

输入 #2

12 2
4 1
8 1

输出 #2

WIN

输入 #3

1 1
1 2

输出 #3

LOSE

注意

在第一个示例中,第一个城市有 3 个可能要收回的单元格:(2, 1)、(3, 1) 或 (3, 2)。前两种可能性都失败了,因为它们只为另一个城市留下了一个牢房。

然而,回收 (3, 2) 处的单元格后,就没有更多可以回收的单元格了,因此第一个城市获胜。

在第三个示例中,没有可以回收的单元格。