P8018 [COCI 2016/2017 #5] Strelice

Hansel 和 Gretel 正在玩「箭头游戏」。 该游戏在一个 $R$ 行 $S$ 列的棋盘上进行。其中每一个棋格内有一个箭头（$\leftarrow$、$\rightarrow$、$\uparrow$、$\downarrow$ 之一）。 游戏开始后，Hansel 可以选择任意 $K$ 个**不位于最后一列的**棋格进行填涂。接着，Gretel 可以选择**第一列的**任意一个棋格，作为机器人的初始棋格。机器人在放置到初始棋格后将按照箭头的指示自动行走。机器人一旦走到了最后一列，它将立即停止行走。 判定输赢的方式如下： - 如果机器人在有限的时间内停在了最后一列，那么：当且仅当机器人恰好经过一个有色棋格时，判定 Hansel 获胜，否则 Gretel 获胜。 - 如果机器人无法停止行走（即处于无限循环的状态），那么判定 Hansel 获胜。 规定机器人经过的棋格包括初始棋格、终止棋格以及路径上的其它所有棋格。同时，数据保证箭头不会指向棋盘外部。 你的任务是判断 Hansel 是否有必胜的方案（即对于 Gretel 所选择的任意一个合法的初始棋格，Hansel 的填涂方案都可以使自己获胜）。如果有必胜的方案，输出该方案；否则输出 $-1$。

第一行，三个整数 $R,S,K$。 接下来的 $R$ 行，每行 $S$ 个字符 $\texttt L$、$\texttt R$、$\texttt U$ 或 $\texttt D$，分别表示对应棋格内的箭头为 $\leftarrow$、$\rightarrow$、$\uparrow$ 和 $\downarrow$。

如果没有必胜的方案，输出 $-1$。 否则输出 $K$ 行，每行两个整数 $A,B$，表示选择的 $K$ 个将要涂色的棋格。棋格必须互不相同。如果存在多种方案，请输出任意一种。 Special Judge 对输出格式要求较严，因此**请勿在每行行尾添加多余空格。**

**【样例 1 解释】** 填涂 $(4,2)$ 后，无论初始棋格位于第一列的哪里，机器人都会经过 $(4,2)$。 **【样例 2 解释】** 由于需要填涂 $2$ 个棋格，因此至少有一行没有有色棋格。只要 Gretel 选择没有有色棋格的那一行的第一列放置机器人，Gretel 就会获胜。 **【样例 3 图解】**  **【数据规模与约定】** 对于 $100\%$ 的数据，$1 \le R \times S \le 10^6$，$1 \le K \le 50$，$1 \le A \le R$，$1 \le B \lt S$。 **【提示与说明】** 欢迎大家通过私信或发帖对自行编写的 [Special Judge](https://www.luogu.com.cn/paste/k9jt7zoy) 进行 hack。 **题目译自 [COCI 2016-2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #5](https://hsin.hr/coci/archive/2016_2017/contest5_tasks.pdf) _T6 Strelice_。** **本题分值按 COCI 原题设置，满分 $160$。**