#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
struct node{int to,v,nxt;}e[N];int head[N],len;
void add(int x,int y,int c)
{
	e[++len]={y,c,head[x]};head[x]=len;
	e[++len]={x,0,head[y]};head[y]=len;	
}
int cur[N],d[N],st,ed;
bool find()
{
	memset(d,0,sizeof(d));d[st]=1;
	deque<int>q;q.push_back(st);
	while(!q.empty())
	{
		int x=q.front();q.pop_front();
		for(int i=head[x];i;i=e[i].nxt)
		{
			int y=e[i].to;
			if(d[y]==0&&e[i].v)
			{
				d[y]=d[x]+1;
				q.push_back(y);
				if(y==ed)return 1;
			}
		}
	}
	return 0;
}
int flow(int x,int s)
{
	if(x==ed)return s;
	int ans=0;
	for(int i=cur[x];i;i=e[i].nxt)
	{
		int y=e[i].to;
		cur[x]=i;
		if(d[y]==d[x]+1&&e[i].v)
		{
			int sum=flow(y,min(e[i].v,s));
			e[i].v-=sum;
			e[i^1].v+=sum;
			ans+=sum;
			s-=sum;
			if(s==0)break;
		}
	}
	if(ans==0)d[x]=0;
	return ans;
}
int dinic()
{
	int ans=0;
	while(find())
	{
		memcpy(cur,head,sizeof(cur));
		ans+=flow(st,1e18);
	}
	return ans;
}

int n,m,total_cells;
char g[105][105];
int id[105][105];
signed main()
{
	cin>>n>>m;len=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>g[i][j];
			if(g[i][j]=='.')id[i][j]=++total_cells;
			else id[i][j]=0;
		}
	}
	st=0,ed=total_cells+1;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(g[i][j]!='.')continue;
			int u=id[i][j];
			if((i+j)%2==1)
			{
				add(st,u,1);
				int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
				for(int d=0;d<4;d++)
				{
					int ni=i+dx[d],nj=j+dy[d];
					if(ni>=1&&ni<=n&&nj>=1&&nj<=m&&g[ni][nj]=='.')add(u,id[ni][nj],1);
				}
			}
			else add(u,ed,1);
		}
	}
	dinic();
	vector<bool>vis_S(ed+1,0);
	deque<int>q;
	q.push_back(st);
	vis_S[st]=1;
	while(!q.empty())
	{
		int x=q.front();q.pop_front();
		for(int i=head[x];i;i=e[i].nxt)
		{
			int y=e[i].to;
			if(e[i].v&&!vis_S[y])
			{
				vis_S[y]=1;
				q.push_back(y);
			}
		}
	}
	vector<bool>vis_T(ed+1,0);
	deque<int>qt;
	qt.push_back(ed);
	vis_T[ed]=1;
	while(!qt.empty())
	{
		int x=qt.front();qt.pop_front();
		for(int i=head[x];i;i=e[i].nxt)
		{
			int y=e[i].to;
			if(e[i^1].v&&!vis_T[y])
			{
				vis_T[y]=1;
				qt.push_back(y);
			}
		}
	}
	vector<pair<int,int>>ans;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(g[i][j]=='.')
			{
				int u=id[i][j];
				bool left=((i+j)%2==1);
				if((left&&vis_S[u])||(!left&&vis_T[u]))ans.push_back({i,j});
			}
		}
	}
	cout<<ans.size()<<'\n';
	sort(ans.begin(),ans.end());
	for(auto p:ans)cout<<p.first<<' '<<p.second<<'\n';
	return 0;
}

$Proved$ $by$ $Qwen：$

这是一个非常经典的二分图博弈问题。要理解为什么“必胜点一定在所有最大匹配的点上”，我们需要从博弈的策略和二分图匹配的性质来分析。

核心结论

在二分图博弈中（两人轮流移动棋子，不能走重复点，无法移动者输）：

• 先手必胜点：起点属于所有最大匹配的点（即一定在最大匹配中）。
• 先手必败点：起点不属于某个最大匹配的点（即存在一个最大匹配不包含该点）。

理论证明（为什么？）

1. 如果起点“不在”某个最大匹配中（先手必败）

假设存在一个最大匹配 $M$ 不包含起点 $S$。

• 先手的第一步：先手必须从 $S$ 走到一个相邻点 $v$。因为 $M$ 是最大匹配，且 $S$ 未被匹配，所以 $v$ 一定在 $M$ 中被匹配（否则 $S-v$ 就是一条增广路，与 $M$ 是最大匹配矛盾）。
• 后手的策略：后手只需要沿着匹配边 $M$ 走到 $v$ 的匹配点 $u$。
• 后续博弈：此时，先手又面临一个“未匹配点”（因为 $u$ 的匹配点 $v$ 已经被走过了）。后手始终可以沿着匹配边走，而先手只能走非匹配边。
• 结局：因为图是有限的，且后手总能走到匹配点，最终先手一定会无路可走。后手必胜。

2. 如果起点“在”所有最大匹配中（先手必胜）

假设起点 $S$ 在所有最大匹配中。

• 先手的策略：先手选择任意一个包含 $S$ 的最大匹配 $M$，并沿着 $M$ 中的匹配边走向 $S$ 的匹配点 $v$。
• 局面转换：此时，棋子位于 $v$，且 $S$ 和 $v$ 都被访问过。对于剩下的图，后手相当于面对一个“起点不在最大匹配中”的局面（因为 $v$ 的匹配点 $S$ 没了，后手现在处于非匹配点）。
• 结局：根据上面的结论，现在的“先手”（即原后手）必败。原先后手必败，即原先后手必胜。

直观举例

例子 1：星型图（中心点必胜，叶子点必败）

    2
    |
3 - 1 - 4

• 最大匹配：只能是 (1,2)、(1,3) 或 (1,4) 中的一个。
• 分析：
  • 点 1 在所有最大匹配中 $\rightarrow$ 必胜点。
  • 点 2, 3, 4 不在所有最大匹配中（例如匹配 (1,3) 就不包含 2） $\rightarrow$ 必败点。
• 博弈过程：
  • 若起点是 1：先手走 2，后手无路可走，先手胜。
  • 若起点是 2：先手只能走 1，后手走 3，先手无路可走，先手败。

例子 2：长链（所有点都必胜）

1 - 2 - 3 - 4

• 最大匹配：唯一的最大匹配是 (1,2) 和 (3,4)。
• 分析：所有点都在这个唯一的最大匹配中 $\rightarrow$ 全是必胜点。
• 博弈过程：
  • 若起点是 1：先手走 2，后手走 3，先手走 4，后手无路可走，先手胜。
  • 若起点是 2：先手走 1，后手无路可走，先手胜。

补充：残量网络 BFS 的作用

在你提供的代码中，vis_S 和 vis_T 标记的点，实际上是存在最大匹配不包含的点（即必败点）。

• 从 S 出发 BFS 能到达的左部点：说明存在增广路，该点可以是未匹配点 $\rightarrow$ 必败点。
• 从 T 出发反图 BFS 能到达的右部点：同理 $\rightarrow$ 必败点。

代码中 ans 收集的是这些点，说明该题求的可能是后手必胜点（或先手必败点）。如果要求先手必胜点，只需取这些点的补集即可。

#include<bits/stdc++.h>
using namespace std;
const int N=105,M=10005;
int n,m;
int mp[N][N],too;
char s[N][N];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
vector<int>e[M];
int s1,b[M],c[M],s2;
int vis[M],tim,lk[M];
struct mo{
	int x,y;
}st[M];
int he;
int dfs(int u){
	for(auto v:e[u]){
		if(vis[v]!=tim){
			vis[v]=tim;
			if(!lk[v]||dfs(lk[v])){
				st[++he]=(mo){v,lk[v]};
				lk[v]=u;
				return 1;
			}
		}
	}return 0;
}
int ans;
int o[N][N];
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){cin>>(s[i]+1);
		for(int j=1;j<=m;j++)if(s[i][j]=='.'){mp[i][j]=++too;if((i+j)&1)b[++s1]=too;else c[++s2]=too;}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(!mp[i][j])continue;
			for(int k=0;k<4;k++){
				int px=i+dx[k],py=j+dy[k];
				if(mp[px][py]){
					e[mp[i][j]].emplace_back(mp[px][py]);
				}
			}
		}
	}int mx=0;
	for(int i=1;i<=s1;i++){++tim;
		mx+=dfs(b[i]);
	}he=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(s[i][j]=='.'){
				if(!(i+j&1)){++tim;
					if(!lk[mp[i][j]]){
						ans++;
						o[i][j]=1;
						continue;
					}vis[mp[i][j]]=tim;
					if(dfs(lk[mp[i][j]])){
						ans++;
						o[i][j]=1;
					}
					while(he)lk[st[he].x]=st[he].y,he--;
				}
			}
		}
	}
	for(int i=1;i<=too;i++)lk[i]=vis[i]=0;
	tim=0;
	for(int i=1;i<=s2;i++){
		++tim;
		dfs(c[i]);
	}he=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(s[i][j]=='.'){
				if((i+j&1)){++tim;
					if(!lk[mp[i][j]]){
						ans++;
						o[i][j]=1;
						continue;
					}vis[mp[i][j]]=tim;
					if(dfs(lk[mp[i][j]])){
						ans++;
						o[i][j]=1;
					}
					while(he){
						lk[st[he].x]=st[he].y,he--;
					}
				}
			}
		}
	}cout<<ans<<"\n";
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(o[i][j])cout<<i<<" "<<j<<"\n";
		}
	}
	return 0;
}