[NOI2011] 兔兔与蛋蛋游戏

题目描述

这些天,兔兔和蛋蛋喜欢上了一种新的棋类游戏。 这个游戏是在一个 $n$ 行 $m$ 列的棋盘上进行的。游戏开始之前,棋盘上有一个格子是空的,其它的格子中都放置了一枚棋子,棋子或者是黑色,或者是白色。 每一局游戏总是兔兔先操作,之后双方轮流操作,具体操作为: * 兔兔每次操作时,选择一枚与空格相邻的白色棋子,将它移进空格。 * 蛋蛋每次操作时,选择一枚与空格相邻的黑色棋子,将它移进空格。 第一个不能按照规则操作的人输掉游戏。为了描述方便,下面将操作“将第x行第y列中的棋子移进空格中”记为 $M(x,y)$。 例如下面是三个游戏的例子。 ![](https://cdn.luogu.com.cn/upload/image_hosting/6wfmhuf2.png) ![](https://cdn.luogu.com.cn/upload/image_hosting/j7vox6n7.png) ![](https://cdn.luogu.com.cn/upload/image_hosting/er1t5wpb.png) 最近兔兔总是输掉游戏,而且蛋蛋格外嚣张,于是兔兔想请她的好朋友——你——来帮助她。她带来了一局输给蛋蛋的游戏的实录,请你指出这一局游戏中所有她“犯错误”的地方。 注意: * 两个格子相邻当且仅当它们有一条公共边。 * 兔兔的操作是“犯错误”的,当且仅当,在这次操作前兔兔有必胜策略,而这次操作后蛋蛋有必胜策略。

输入输出格式

输入格式


输入的第一行包含两个正整数 $n,m$。 接下来 $n$ 行描述初始棋盘。其中第 $i$ 行包含 $m$ 个字符,每个字符都是大写英文字母 `X`、大写英文字母 `O` 或点号 `.` 之一,分别表示对应的棋盘格中有黑色棋子、有白色棋子和没有棋子。其中点号 `.` 恰好出现一次。 接下来一行包含一个整数 $k$($1\leq k\leq 1000$) ,表示兔兔和蛋蛋各进行了 $k$ 次操作。 接下来 $2k$ 行描述一局游戏的过程。其中第 $2i - 1$ 行是兔兔的第 $i$ 次操作(编号为 $i$ 的操作) ,第 $2i$ 行是蛋蛋的第 $i$ 次操作。每个操作使用两个整数 $x,y$ 来描述,表示将第 $x$ 行第 $y$ 列中的棋子移进空格中。 输入保证整个棋盘中只有一个格子没有棋子, 游戏过程中兔兔和蛋蛋的每个操作都是合法的,且最后蛋蛋获胜。

输出格式


输出文件的第一行包含一个整数 $r$,表示兔兔犯错误的总次数。 接下来 $r$ 行按递增的顺序给出兔兔“犯错误”的操作编号。其中第 $i$ 行包含一个整数 $a_i$ 表示兔兔第 $i$ 个犯错误的操作是他在游戏中的第 $a_i$ 次操作。

输入输出样例

输入样例 #1

1 6 
XO.OXO 
1 
1 2 
1 1 

输出样例 #1

1
1

输入样例 #2

3 3 
XOX 
O.O 
XOX 
4 
2 3 
1 3 
1 2 
1 1 
2 1 
3 1 
3 2 
3 3 

输出样例 #2

0

输入样例 #3

4 4 
OOXX 
OXXO 
OO.O 
XXXO 
2 
3 2 
2 2 
1 2 
1 3 

输出样例 #3

2
1
2

说明

对于 $100\%$ 的数据,$1\leq n\leq 40$,$1 \leq m\leq 40$,$1\leq k\leq 1000$。 |测试点编号|$n$|$m$| |:-:|:-:|:-:| |$1,2$|$n=1$|$1\leq m\leq 20$| |$3$|$n=3$|$m=4$| |$4,5$|$n=4$|$m=4$| |$6,7$|$n=4$|$m=5$| |$8$|$n=3$|$m=7$| |$9\sim 14$|$n=2$|$1\leq m\leq 40$| |$15,16$|$1\leq n\leq 16$|$1\leq m\leq 16$| |$17\sim 20$|$1\leq n\leq 40$|$1\leq m\leq 40$|