P17872 [FJCPC 2026] 限号出行

P 国是一个神奇的国度，在这里，所有的车牌都是长度恰好为 $k$ 且仅包含小写英文字母的字符串。 然而，再神奇的国度也避免不了交通堵塞的问题。为此，P 国采用"限号出行"的方式进行分流。具体来说，决定一个车牌 $s$ 在当天能否出行的是若干条形如 $(x_i,y_i)$ 的规则，若 $s$ 中存在一个位置 $1\le j

**本题包含多组测试数据。** 第一行包含一个整数 $T$（$1\le T\le 10^5$），表示测试数据的组数。 接下来，对于每组测试数据： 第一行包含三个非负整数，分别表示 $n,m$ 和 $k$（$1\le k\le n\le \sum n\le 2\times 10^5$，$0\le m\le \min(n,26)^2$）。 第二行包含一个长度为 $n$ 的字符串，表示 $t$。 接下来 $m$ 行，每行包含两个由单个空格隔开的小写英文字母，分别表示 $x_i$ 和 $y_i$，保证 $\forall i\ne j,(x_i,y_i)\ne(x_j,y_j)$。

对于每组测试数据，输出一行一个字符串，若有解则输出字典序最小的可行车牌，否则输出 `-1`。