太阳之华
题号:NC267930
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 768 M,其他语言1536 M
64bit IO Format: %lld

题目描述

太阳之华下
众生在游戏
白垩色的王子摆放了一个 n \times m 的棋盘,游戏开始时棋盘上的每一个格子要么是红色 `#` 的,要么是蓝色 `.` 的。
游戏规则是这样的:红方先手,双方交替进行游戏。每一方在自己的回合都可以选择一个由自己的颜色的格子组成的四连通区域,然后对于这个四连通区域的每一个格子:如果这个格子的上下左右有和该格子颜色不同的格子的话,就将这些格子染成该格子的颜色。当场上均为蓝色格子时,蓝方胜利;当场上均为红方格子时,红方胜利。
注:四连通区域指的是从区域内每一格出发,可通过四个方向,即上、下、左、右这四个方向的移动的组合,在不越出区域的前提下,到达区域内的任意格子。
例如:

这是一张 4 \times 4 的棋盘,左图中,红方选择较上方的那个四连通区域进行染色,染色之后,棋盘会变成右图这个样子。
现在给出初始棋盘,询问如果双方都足够聪明,有没有一方一定能够获得游戏胜利,或者是游戏永远结束不了而将以平局告终。

输入描述:

第一行输入一个整数 T(1 \le T \le 100),表示数据组数。
对于每一组数据,第一行输入两个整数 n,m(1 \le n \le \sum n \le 2000,1 \le m \le \sum m \le 2000),表示这个棋盘有 nm 列。
接下来 n 行,每行包含 m 个字符 c_{i,j},保证 c_{i,j} 一定为 `#` 或 `.`。`#` 表示第 i 行第 j 列在游戏开始时的颜色为红色,`.` 表示第 i 行第 j 列在游戏开始时的颜色为蓝色。

输出描述:

对于每一组数据,输出一行一个字符串 SS 一定为 "Red"、"Blue"、"Draw" 中的一种(不含引号),分别表示红方能获胜、蓝方能获胜、游戏永远无法结束。
示例1

输入

复制
3
3 5
#.###
#.#.#
#.###
1 6
###...
2 3
...
...

输出

复制
Red
Draw
Blue

说明

对于第一组数据,红方第一步选择较右边那个四联通块即可获胜。