C0787 [ZJOI2009]染色游戏

内存限制:256 MB 时间限制:1000 ms

题目描述

一共 $n×m$ 个硬币,摆成 $n×m$ 的长方形。dongdong和xixi玩一个游戏,每次可以选择一个连通块,并把其中的硬币全部翻转,但是需要满足存在一个硬币属于这个连通块并且所有其他硬币都在它的左上方(可以正左方也可以正上方),并且这个硬币是从反面向上翻成正面向上。dongdong 和 xixi 轮流操作。如果某一方无法操作,那么他就输了。dongdong 先进行第一步操作,假设双方都采用最优策略。问 dongdong 是否有必胜策略。

输入格式

第一行一个数 $T$,表示他们一共玩 $T$ 局游戏。

接下来是 $T$ 组游戏描述。每组游戏第一行两个数 $n,m$,接下来 $n$ 行每行 $m$ 个字符,第 $i$ 行第 $j$ 个字符如果是“H”表示第 $i$ 行第 $j$ 列的硬币是正面向上,否则是反面向上。

第 $i$ 行 $j$ 列的左上方是指行不超过 $i$ 并且列不超过 $j$ 的区域。

$1≤n,m≤100,1≤T≤50$。

输出

对于每局游戏,输出一行。

如果 dongdong 存在必胜策略则输出“-_-”(不含引号)否则输出“=_=”(不含引号)。

注意输出的都是半角符号,即三个符号 ASCII 码分别为 $45,61,95$

样例

样例输入 1

3 2 3 HHH HHH 2 3 HHH TTH 2 1 T H

样例输出 1

=_= -_- -_-

提示