【NOI2017】游戏 排行榜

---

时间限制： 1 s
空间限制： 524288 KB

题目描述

小 L 计划进行 $n$ 场游戏，每场游戏使用一张地图，小 L 会选择一辆车在该地图上完成游戏。

小 L 的赛车有三辆，分别用大写字母 $A$、$B$、$C$ 表示。地图一共有四种，分别用小写字母 $x$、$a$、$b$、$c$ 表示。

其中，赛车 $A$ 不适合在地图 $a$ 上使用，赛车 $B$ 不适合在地图 $b$ 上使用，赛车 $C$ 不适合在地图 $c$ 上使用，而地图 $x$ 则适合所有赛车参加。

适合所有赛车参加的地图并不多见，最多只会有 $d$ 张。

$n$ 场游戏的地图可以用一个小写字母组成的字符串描述。例如：$S=\texttt{xaabxcbc}$ 表示小 L 计划进行 $8$ 场游戏，其中第 $1$ 场和第 $5$ 场的地图类型是 $x$，适合所有赛车，第 $2$ 场和第 $3$ 场的地图是 $a$，不适合赛车 $A$，第 $4$ 场和第 $7$ 场的地图是 $b$，不适合赛车 $B$，第 $6$ 场和第 $8$ 场的地图是 $c$，不适合赛车 $C$。

小 L 对游戏有一些特殊的要求，这些要求可以用四元组 ($i, h_i, j, h_j$) 来描述，表示若在第 $i$ 场使用型号为 $h_i$ 的车子，则第 $j$ 场游戏要使用型号为 $h_j$ 的车子。

你能帮小 L 选择每场游戏使用的赛车吗？如果有多种方案，输出任意一种方案。

如果无解，输出 -1。

输入格式

从标准输入读入数据。

输入第一行包含两个非负整数 $n, d$。

输入第二行为一个字符串 $S$。

$n, d, S$ 的含义见题目描述，其中 $S$ 包含 $n$ 个字符，且其中恰好 $d$ 个为小写字母 $x$。

输入第三行为一个正整数 $m$ ，表示有 $m$ 条用车规则。

接下来 $m$ 行，每行包含一个四元组 $i,h_i,j,h_j$ ，其中 $i,j$ 为整数，$h_i,h_j$ 为字符 $A$ 、$B$ 或 $C$，含义见题目描述。

输出格式

输出到标准输出。

输出一行。

若无解输出 -1。

样例输入

样例输出

样例解释

小 L 计划进行 $3$ 场游戏，其中第 $1$ 场的地图类型是 $x$，适合所有赛车，第 $2$ 场和第 $3$ 场的地图是 $c$，不适合赛车 $C$。

小 L 希望：若第 $1$ 场游戏使用赛车 $A$，则第 $2$ 场游戏使用赛车 $B$。

那么为这 $3$ 场游戏分别安排赛车 $A$、$B$、$A$ 可以满足所有条件。

若依次为 $3$ 场游戏安排赛车为 $BBB$ 或 $BAA$ 时，也可以满足所有条件，也被视为正确答案。

但依次安排赛车为 $AAB$ 或 $ABC$ 时，因为不能满足所有条件，所以不被视为正确答案。

数据范围与提示

测试点编号	$n$	$d$	$m$	其他性质
1	$\le 2$	$0$	$\le 4$	无
2		$\le n$
3	$\le 5$	$0$	$\le 10$
4		$\le n$
5	$\le 10$	$0$	$\le 20$
6		$\le 8$
7	$\le 20$	$0$	$\le 40$	S中只包含c
8				无
9		$\le 8$		S中只包含x或c
10				无
11	$\le 100$	$0$	$\le 200$	S中只包含c
12				无
13		$\le 8$		S中只包含x或c
14				无
15	$\le 5000$	$0$	$\le 10000$
16		$\le 8$		S中只包含x或c
17				无
18	$\le 50000$	$0$	$\le 100000$
19		$\le 8$		S中只包含x或c
20				无

题目来源

NOI 2017 Day 1

---

---