More Reclamation

题目描述

In a far away land, there are two cities near a river. One day, the cities decide that they have too little space and would like to reclaim some of the river area into land. The river area can be represented by a grid with $ r $ rows and exactly two columns — each cell represents a rectangular area. The rows are numbered $ 1 $ through $ r $ from top to bottom, while the columns are numbered $ 1 $ and $ 2 $ . Initially, all of the cells are occupied by the river. The plan is to turn some of those cells into land one by one, with the cities alternately choosing a cell to reclaim, and continuing until no more cells can be reclaimed. However, the river is also used as a major trade route. The cities need to make sure that ships will still be able to sail from one end of the river to the other. More formally, if a cell $ (r,c) $ has been reclaimed, it is not allowed to reclaim any of the cells $ (r-1,3-c) $ , $ (r,3-c) $ , or $ (r+1,3-c) $ . The cities are not on friendly terms, and each city wants to be the last city to reclaim a cell (they don't care about how many cells they reclaim, just who reclaims a cell last). The cities have already reclaimed $ n $ cells. Your job is to determine which city will be the last to reclaim a cell, assuming both choose cells optimally from current moment.

输入输出格式

输入格式

The first line consists of two integers $ r $ and $ n $ ( $ 1<=r<=100,0<=n<=r $ ). Then $ n $ lines follow, describing the cells that were already reclaimed. Each line consists of two integers: $ r_{i} $ and $ c_{i} $ ( $ 1<=r_{i}<=r,1<=c_{i}<=2 $ ), which represent the cell located at row $ r_{i} $ and column $ c_{i} $ . All of the lines describing the cells will be distinct, and the reclaimed cells will not violate the constraints above.

输出格式

Output "WIN" if the city whose turn it is to choose a cell can guarantee that they will be the last to choose a cell. Otherwise print "LOSE".

输入输出样例

输入样例 #1

3 1
1 1

输出样例 #1

WIN

输入样例 #2

12 2
4 1
8 1

输出样例 #2

WIN

输入样例 #3

1 1
1 2

输出样例 #3

LOSE

说明

In the first example, there are 3 possible cells for the first city to reclaim: $ (2,1) $ , $ (3,1) $ , or $ (3,2) $ . The first two possibilities both lose, as they leave exactly one cell for the other city. However, reclaiming the cell at $ (3,2) $ leaves no more cells that can be reclaimed, and therefore the first city wins. In the third example, there are no cells that can be reclaimed.

题意翻译

有一个 $r\times2$ 的矩形，两个人轮流的在矩形上面减去一个 $1\times1$ 的小正方形，要求在减的过程中，不能使矩形“断开”，也就是说，如果一个人减去了 $(i, 1)$ 这个矩形，那么，$(i-1, 2)$, $(i+1, 2)$, $(i, 2)$ 这三个小正方形不能再被减去了，因为一旦减去它们中的一个，整个矩形就会被“剪断”。 现在给你一个 $r$ 和 $n$ $(1 ≤ r ≤ 100, 0 ≤ n ≤ r)$，表示有一个 $r\times2$ 矩形，已经有了 $n$ 个位置被减去了，再给 $n$ 个位置的坐标，题目保证开始的状态矩形不会被剪断. 现在问，对于当前的状态，先手是否必胜，必胜输出```WIN```,否则输出```LOSE```。 翻译：@[linzhicong2011](https://www.luogu.com.cn/user/661534)。