P11088 [ROI 2021] Punched Cards (Day 1).

Translated from [ROI 2021 D1T1](https://neerc.ifmo.ru/school/archive/2020-2021/ru-olymp-roi-2021-day1.pdf).

A punched card is a strip consisting of $m$ small squares, where each square either contains a lowercase English letter or is a hole. There are $n$ such punched cards. Given a string $s$ of length $m$, arrange all punched cards in some order so that after stacking them from top to bottom, the result becomes $s$. In other words, you need to determine the order of the punched cards. When they are stacked together, for every position $i(1 \le i \le m)$, the $i$-th character of the string $s$ must be the same as the character on the first punched card (from top to bottom) that has a letter at position $i$. If for some $i$, there is no punched card that has a letter at this position, then it is impossible to obtain the target string $s$.

The first line contains two integers $n,m(1 \le n,m \le 10^5)$, representing the number of punched cards and the number of squares. The second line contains a string $s$ of length $m$, consisting of lowercase English letters. In the next $n$ lines, each line describes one punched card. First, an integer $k_i(0\le k_i\le m)$ is given, meaning how many positions on this punched card contain letters. It is guaranteed that the sum of all $k_i$ does not exceed $2\times 10^5$. Then follows the description of the letters on this punched card: for each integer $j(1 \le j \le k_i)$, there is an integer $a_{i,j}$ and a character $c_{i,j}$ ($1 \le a_{i,j} \le m$, $c_{i,j}$ is a lowercase English letter), meaning that the character at position $a_{i,j}$ is $c_{i,j}$. All other positions are holes. It is guaranteed that the positions with letters on each punched card are in increasing order, i.e., $\forall1 \le j < k_,a_{i,j} < a_{i,{j+1}}$.

If there exists a correct way to arrange the punched cards, output $n$ integers $p_1,p_2,\dots,p_n(1 \le pi \le n)$, where $p_1$ is the index of the top card, $p_2$ is the index of the second card, and so on, and $p_n$ is the index of the bottom card. If there are multiple possible answers, you may output any of them. If there is no correct arrangement, output `-1`.

Explanation for sample $2$:  Constraints: | Subtask | Score | $n\le$ | $m\le$ | | :----------: | :----------: | :----------: | :----------: | | $1$ | $15$ | $8$ | $100$ | | $2$ | $35$ | $100$ | $100$ | | $3$ | $50$ | $10^5$ | $10^5$ | Translated by ChatGPT 5