🔴🔵 B1《点阵封圈游戏》 🧩

在 兔猫信奥学院 的棋盘室里，小兔和小猫围着加菲老师摆出的一个点阵玩游戏。 Alice 和 Bob 的规则很古老也很简单：

1. 先画出一个 $n \times n$ 的点阵（点的坐标用整数表示）。
2. 然后两人轮流在相邻的点之间画边（红边或蓝边不影响判定，本题只关心“是否形成封闭圈”）。
3. 当某一步画完边后，出现了一个封闭的圈（围成的面积不要求为 1，可以很大），则“封圈”的那个人立即获胜，游戏结束。

但由于 $n \le 200$，棋盘很大，步骤也很多，他们甚至不知道游戏在第几步就已经结束了。 请你根据已经画出的 $m$ 条边，判断：

• 游戏是在第几步第一次出现封闭圈并结束？
• 如果直到第 $m$ 步仍未出现封闭圈，则输出 draw。

📌 边的表示方式

每一步只会画 一条边，输入用三元组 (x, y, dir) 表示：

• (x, y)：表示画线的起点坐标

• dir 是一个字符：

  • D：从 $(x, y)$ 向下 连接一条边（到 $(x, y+1)$）
  • R：从 $(x, y)$ 向右 连接一条边（到 $(x+1, y)$）

保证：

• 输入中不会出现重复边
• 所有操作都是合法的（不会连出点阵范围外）

🧠 判定说明

• 当你画出一条边后，如果这条边使得图中出现了任意一个环（封闭圈），则游戏在这一刻结束。
• 你需要输出：第一次出现环的步数（从 1 开始计数）。
• 若直到画完 $m$ 条边也没有环，则输出 draw。

输入格式

第一行两个整数 $n, m$。

接下来 $m$ 行，每行三个输入：

• 两个整数 $x, y$
• 一个字符 D 或 R

输出格式

输出一行：

• 若第 $k$ 步第一次出现封闭圈，输出整数 $k$
• 否则输出 draw

3 5
1 1 D
1 1 R
1 2 D
2 1 R
2 2 D

4

🖼️ 样例封圈示意（必须原样保留）

提示：样例中在第 4 步后，某条新边使得图中首次出现封闭圈，因此输出 4。

数据范围

• $1 \le n \le 200$
• $1 \le m$（具体上限以题库为准，但可能较大）

（提示：需要高效判断“加边后是否第一次成环”。）