Description：

给一个棋盘，有一些点不能经过，先手先选择最开始棋子的位置，然后后手和先手轮流移动棋子，最后不能操作的人输，问先手是否能赢，如果能赢，哪些点可以作为最开始放置棋子的位置。

$1\leqslant n,m\leqslant 100$

Solution：

二分图博弈。

先把棋盘黑白染色，然后能移动的格子之间连边，这样就得到了一个二分图，那么先手输当且仅当这个二分图存在完备匹配，因为后手第一次将棋子沿着匹配边走，那么先手就只能走非匹配边，因为这个点只有一条匹配边，这样后手又可以走匹配边，所以先手每次操作都会走到一个之前没有走过的点，那么后手只要走这个点的匹配边即可，所以最后一定是先手先无路可走。

否则的话，先手可以先选一个不在最大匹配上的点，那么后手一定会走到一个匹配点，不然的话这两个点可以形成一个新的匹配，然后先手再按照上面的做法操作即可。

关于输出方案的话，我们发现要求的实际上就是有哪些点可以不在最大匹配上，结论就是先处理 $X$ 集合，先得到任意一个最大匹配，然后从所有这个匹配中非匹配点出发走交错路，遍历到的 $X$ 集合中的点就可以和这个点交换，即变换一半的交错路把这个点换成非匹配点，这些点都可以不在最大匹配中，然后再对 $Y$ 集合进行同样的操作即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 110

char c[MAXN][MAXN];

char getc()

{

	register char c = getchar();

	while(c != '#' && c != '.')c = getchar();

	return c;

}

struct edge

{

	int to,nxt;

}e[MAXN * MAXN * 8];

int edgenum = 0;

int lin[MAXN * MAXN] = {0};

void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return;

}

int match[MAXN * MAXN];

int mat[MAXN * MAXN];

bool v[MAXN * MAXN];

int mx[4] = {0,0,1,-1};

int my[4] = {1,-1,0,0};

int to(int i,int j){return (i - 1) * m + j;}

bool find(int k)

{

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(!v[e[i].to])

		{

			v[e[i].to] = true;

			if(match[e[i].to] == -1 || find(match[e[i].to]))

			{

				match[e[i].to] = k;

				mat[k] = e[i].to;

				return true;

			}

		}

	}

	return false;

}

bool tag1[MAXN * MAXN],tag2[MAXN * MAXN];

void mark1(int k)

{

	tag1[k] = true;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(!tag1[e[i].to])

		{

			tag1[e[i].to] = true;

			if(match[e[i].to] == -1)continue;

			mark1(match[e[i].to]);

		}

	}

	return;

}

void mark2(int k)

{

	tag2[k] = true;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(!tag2[e[i].to])

		{

			tag2[e[i].to] = true;

			if(mat[e[i].to] == 0)continue;

			mark2(mat[e[i].to]);

		}

	}

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)

		for(int j = 1;j <= m;++j)

			c[i][j] = getc();

	int cnt = 0;

	for(int i = 1;i <= n;++i)

	{

		for(int j = 1;j <= m;++j)

		{

			if(c[i][j] == '#')continue;

			++cnt;

			if((i + j) % 2 == 0)continue;

			for(int k = 0;k < 4;++k)

				if(1 <= i + mx[k] && i + mx[k] <= n && 1 <= j + my[k] && j + my[k] <= m && c[i + mx[k]][j + my[k]] == '.')

					add(to(i,j),to(i + mx[k],j + my[k]));

		}

	}

	memset(match,-1,sizeof(match));

	int ans = 0;

	for(int i = 1;i <= n;++i)

	{

		for(int j = 1;j <= m;++j)

		{

			if((i + j) % 2 == 0)continue;

			if(c[i][j] == '#')continue;

			memset(v,false,sizeof(v));

			if(find(to(i,j)))++ans;

		}

	}

	if(ans * 2 == cnt)

	{

		puts("LOSE");

		return 0;

	}

	else

	{

		puts("WIN");

		for(int i = 1;i <= n;++i)

		{

			for(int j = 1;j <= m;++j)

			{

				if(c[i][j] == '#')continue;

				if((i + j) % 2 == 0)continue;

				if(mat[to(i,j)] == 0)mark1(to(i,j));

			}

		}

		for(int i = 1;i <= n;++i)

		{

			for(int j = 1;j <= m;++j)

			{

				if(c[i][j] == '#')continue;

				if((i + j) % 2 == 1)continue;

				if(match[to(i,j)] == -1)mark2(to(i,j));

			}

		}

		for(int i = 1;i <= n;++i)

		{

			for(int j = 1;j <= m;++j)

			{

				if((i + j) % 2 == 0 && tag2[to(i,j)])printf("%d %d\n",i,j);

				if((i + j) % 2 == 1 && tag1[to(i,j)])printf("%d %d\n",i,j);

			}

		}

	}

	return 0;

}