P13990 [PO Final 2023] 漏斗 / Hopper

1G, 8s, hoppers2 **请注意本题特殊的时间限制。**

Joshua 在 Minecraft 中建造了一个工厂，它由一个网格组成，网格的每个单元格里都有一个所谓的漏斗（hopper）。一个漏斗可以在其内部存放一件物品，并指向另一个漏斗，该漏斗要么位于它的正上方、正下方、左侧或右侧。每秒一次，若某个漏斗内有物品，它会将该物品推送到其所指向的那个漏斗。有时这会导致某个漏斗在同一时刻同时拥有多件物品。显然这不可行，因为在那一秒内被推入该漏斗的所有物品都会被销毁。 Joshua 希望拥有一个碰撞不多且稳定的工厂。他因此给出了一份关于物品如何摆放以及工厂应当如何布局的方案，并且现在想要知道对每件物品来说，它会发生碰撞还是会在工厂中无限循环。对于所有会发生碰撞的物品，他还想知道碰撞发生的位置，以便之后更新设计。请你编写程序帮助他！  $\qquad$  图 1：样例 1 中的工厂在启动前以及 1 秒后的状态。注意中央格子里有 3 个物品发生了碰撞。

第一行包含整数 $ R, C $（满足 $ 2 \le R \cdot C \le 10^6 $）和 $ N $（$ 1 \le N \le 10^5 $），分别表示网格的行数与列数，以及方案中的物品数量。 接下来有 $ R $ 行描述工厂的布局。每一行由一个长度为 $ C $ 的字符串组成。网格中的每个字符表示该格子里的漏斗所指向的方向。字符只会是 `v`（向下）、``（向右）。保证每个漏斗都指向另一个漏斗。 随后有 $ N $ 行，每行包含两个整数 $ P_r $（$ 0 \le P_r \le R - 1 $）和 $ P_c $（$ 0 \le P_c \le C - 1 $），表示第 $ i $ 个物品的起始行与列。保证初始时没有任何漏斗同时包含两件或以上的物品。

按输入顺序对每件物品各输出一行：如果该物品永远不会与任何东西发生碰撞，则输出字符串 $\texttt{cycle}$；否则输出 “$ r\ c $”，表示它在第 $ r $ 行第 $ c $ 列的漏斗处发生碰撞（从 0 开始计数）。

### 子任务 **本题采用捆绑测试。** | 子任务编号 | 分值 | 限制 | |:-:|:-:|-------------| | $1$ | $10$ | $ R \cdot C \le 1000,\ N \le 1000 $ | | $2$ | $35$ | $ N \le 1000 $ | | $3$ | $15$ | 若某个漏斗属于一个环路，则最多只有一个其他漏斗指向它。 | | $4$ | $25$ | 没有漏斗指向上方。 | | $5$ | $15$ | 无额外限制。 |