P11088 [ROI 2021] 穿孔卡片 (Day 1)

翻译自 [ROI 2021 D1T1](https://neerc.ifmo.ru/school/archive/2020-2021/ru-olymp-roi-2021-day1.pdf)。

穿孔卡片是一条由 $m$ 个小方格组成的带状物，每个小方格要么包含一个小写英文字母，要么是一个孔洞。 有 $n$ 张这样的穿孔卡片。给定一个长度为 $m$ 的字符串 $s$，将所有的穿孔卡片按照一定顺序排列，使得将它们从上到下依次叠放后可以变成 $s$。换句话说，要确定穿孔卡片的顺序，它们将叠放在一起，并考虑任意位置 $i(1 \le i \le m)$，字符串 $s$ 的第 $i$ 个字符必须与第 $i$ 个位置上第一个包含字母的那张穿孔卡片上的字符相同。 如果对于某个 $i$，不存在任何一个穿孔卡片上的这个位置有字母，那么就无法得到目标字符串 $s$。

第一行包含两个整数 $n,m(1 \le n,m \le 100,000)$，分别表示穿孔卡片的数量和格子的数量。 第二行包含一个长度为 $m$ 的字符串 $s$，由小写英文字母组成。 接下来的 $n$ 行中，每行输入一张穿孔卡片的信息。 先输入一个整数 $k_i(0\le k_i\le m)$，表示该穿孔卡片上有多少个带字母的位置。保证所有 $k_i$ 的总和不超过 $200,000$。 然后是该穿孔卡片上字母的描述：对于每个整数 $j(1 \le j \le k_i)$，有一个整数 $a_{i,j}$ 和一个字符 $c_{i,j}$（$1 \le a_{i,j} \le m$，$c_{i,j}$ 是一个小写英文字母），表示位置 $a_{i,j}$ 上的字符是 $c_{i,j}$。其余位置都是孔洞。保证每张穿孔卡片上的带字母的位置按升序排列，即 $\forall1 \le j < k_,a_{i,j} < a_{i,{j+1}}$。

如果存在一种正确排列穿孔卡片的方法，输出 $n$ 个整数 $p_1,p_2,\dots,p_n(1 \le pi \le n)$，其中 $p_1$ 表示最上面的卡片编号，$p_2$ 表示第二张卡片编号，依此类推，$p_n$ 表示最下面的卡片编号。 如果存在多个可能的答案，可以输出任意一个。如果不存在一种正确排列穿孔卡片的方法，输出 `-1`。

样例 $2$ 解释：  数据范围： | 子任务 | 分值 | $n\le$ | $m\le$ | | :----------: | :----------: | :----------: | :----------: | | $1$ | $15$ | $8$ | $100$ | | $2$ | $35$ | $100$ | $100$ | | $3$ | $50$ | $100000$ | $100000$ |