P14999 [Nordic OI 2019] Thieves and Prisons

Special Judge 来自于 [LibreOJ](https://loj.ac/p/4248)。

有 $n$ 个盗贼和 $k$ 座监狱。一个盗贼要么正在逃亡，要么已被关押在某座监狱中。初始时，所有盗贼都在逃亡。 一个正在逃亡的盗贼可以被警察抓住，随后被关进其中一座监狱。一个正在逃亡的盗贼也可以打开某座监狱的大门。当大门被打开时，关押在该监狱中的所有盗贼都会被释放。打开一座空监狱的大门是毫无意义的，因此这种情况永远不会发生。 你得到一个包含 $m$ 个事件的列表，事件的格式为“盗贼 $x$ 被抓住”或“盗贼 $x$ 打开了某座监狱的大门”。你的任务是找出一个符合这些事件的监狱分配方案，或者判断这是不可能的。

第一行输入包含三个整数 $n$、$k$ 和 $m$：分别表示盗贼的数量、监狱的数量以及事件的数量。盗贼和监狱的编号分别为 $1, 2, \ldots, n$ 和 $1, 2, \ldots, k$。 此后是 $m$ 行，描述各个事件。每个事件是“C $x$”（盗贼 $x$ 被抓住）或“O $x$”（盗贼 $x$ 打开了某座监狱的大门）。

输出一个有效的监狱分配方案，由 $m$ 个整数组成：每个整数对应相应事件所涉及的监狱。如果不存在解决方案，则输出“IMPOSSIBLE”。

**子任务 1（8 分）** - $1 \leq n, m \leq 10$ - $k = 2$ **子任务 2（13 分）** - $1 \leq n, k, m \leq 10^5$ - $n = k$ **子任务 3（14 分）** - $1 \leq n, m \leq 10^5$ - $k = 2$ **子任务 4（18 分）** - $1 \leq n, k, m \leq 500$ **子任务 5（47 分）** - $1 \leq n, k, m \leq 10^5$ 翻译由 DeepSeek V3 完成