入门⏱ 1000ms💾 256MB#P2279🏷️ 并查集数据结构

题目描述

两人在 $n \times n$ 的点阵上轮流在相邻点之间画线(红蓝交替,规则对称): 每当画下一条线使点阵中首次出现封闭圈,画这条线的人获胜。

给出 $m$ 条线的画线顺序,判断游戏在第几步结束; 若 $m$ 步画完仍未成圈,输出 draw。

输入格式

第一行两个整数 $n, m$; 以下 $m$ 行,每行两个整数 $x, y$ 和一个字符 D(向下画)或 R(向右画)。

输出格式

一行:成圈的步数;未成圈输出 draw。

数据范围

$$n \le 200$$
,边不重复且合法。

样例输入 #1
3 5
1 1 D
1 1 R
1 2 D
2 1 R
样例输出 #1
4
样例输入 #2
2 2
1 1 D
1 1 R
样例输出 #2
draw