QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB

# 8742. 黑白

统计

题目描述

小 I 和小 J 又在玩游戏。

游戏在一个 $n \times m$ 的网格上进行,我们用二元组 $(x,y)$ 描述第 $x$ 行第 $y$ 列的格子,其中 $1 \le x \le n, 1 \le y \le m$。初始时,网格上有至少一个格子是白色的,其他格子是黑色的。

小 I 和小 J 轮流操作,小 I 先手。每次操作时,操作方必须选择恰好一个白色的格子并将其染黑。

称两个格子相邻当且仅当它们共用一条边。若某次操作后,格子 $(1,1)$ 不是白的,或者格子 $(n,m)$ 不是白的,或者无法从 $(1,1)$ 出发,每次经过相邻的白色格子,最终到达 $(n,m)$(即 $(1,1)$ 和 $(n,m)$ 不在同一个白色格子构成的四连通块内),则当前操作方输,另一方胜利。

你作为游戏的观众,想知道在小 I 和小 J 绝顶聪明的情况下,谁会获胜。

输入格式

从标准输入读入数据。

本题有多组测试数据。输入的第一行一个整数 $T (1 \le T \le 100)$ 表示测试数据组数,接下来依次输入每组测试数据。对于每组测试数据,

  • 第一行两个整数 $n, m (2 \le n, m \le 1000)$,表示网格的大小。
  • 接下来 $n$ 行每行一个长度为 $m$、字符集为 BW 的字符串,描述网格初始时的染色情况。其中第 $i$ 行第 $j$ 个字符为 B 表示 $(i,j)$ 初始为黑色,否则为 W 表示 $(i,j)$ 初始为白色。保证初始棋盘上至少有一个白色格子。

保证单个测试点中所有测试数据的 $n \times m$ 的和不超过 $5 \times 10^6$。

输出格式

输出到标准输出。

对于每组测试数据输出一行一个字符,若小 I 必胜输出 I,否则若小 J 必胜输出 J

样例

输入

2
2 2
WB
WW
2 2
WW
WW

输出

J
I

解释

对于第一组测试数据,小 I 只能染黑 $(2,1)$,但染黑 $(2,1)$ 会导致无法仅通过每次移动到相邻的白色格子从 $(1,1)$ 移动到 $(2,2)$,因此无论小 I 如何操作都将失败,故输出 J

对于第二组测试数据,小 I 可以染黑 $(1,2)$,然后无论小 J 如何操作都将失败,故输出 I