| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 57 | 20 | 16 | 43.243% |
На складе фирмы, на базе которой проходит олимпиада по программированию, были обнаружены $n$ перфокарт. Перфокарта представляет собой полоску из $m$ клеточек, каждая из которых либо содержит строчную английскую букву, либо является отверстием.
Жюри олимпиады решило упорядочить все перфокарты так, что если расположить их одну под другой сверху вниз в этом порядке, то получится лозунг олимпиады --- заданная строка $s$ длины $m$.
Иными словами, зафиксируем порядок перфокарт, в котором они будут лежать, и рассмотрим произвольную позицию $i$ (1ドル \le i \le m$). Тогда $i$-й символ строки $s$ должен совпадать с символом на $i$-й позиции самой верхней перфокарты, содержащей на позиции $i$ какую-либо букву. Если для какого-то $i$ ни одной перфокарты с буквой в позиции $i$ нет, то считается, что требуемую строку $s$ получить невозможно.
Помогите жюри понять, в каком порядке необходимо расположить перфокарты.
Рис. 1: Порядок карт из второго примера. Выделены те буквы, которые видны сверху
Первая строка содержит два целых числа $n$ и $m$ (1ドル \le n, m \le 100,000円$), обозначающих число перфокарт и количество клеток соответственно.
Вторая строка содержит строку $s,ドル состоящую из $m$ строчных английских букв.
В $i$-й из следующих $n$ строк находится описание $i$-й перфокарты.
Описание начинается с целого числа $k_i$ (0ドル \le k_i \le m$), обозначающего количество позиций с буквами в этой перфокарте. Гарантируется, что сумма всех значений $k_i$ не превышает 200ドル,000円$.
Далее следует описание букв на этой перфокарте: $k_i$ пар $a_{i,j},ドル $c_{i,j}$ (1ドル \le a_{i,j} \le m,ドル $c_{i,j}$ является строчной английской буквой) для всех целых 1ドル \leq j \leq k_i$; каждая пара обозначает наличие символа $c_{i,j}$ на позиции $a_{i,j}$. Остальные позиции содержат отверстия. Гарантируется, что номера позиций с буквами для одной перфокарты приведены по возрастанию, то есть для любого 1ドル \leq j < k_i$ верно $a_{i,j} < a_{i,j+1}$.
Если способ упорядочить перфокарты требуемым способом существует, выведите $n$ целых чисел $p_1, p_2, \ldots, p_n$ (1ドル \le p_i \le n$), где $p_1$ --- номер самой верхней перфокарты, $p_2$ --- номер второй сверху перфокарты, и так далее до перфокарты $p_n,ドル которая лежит ниже всех. Если возможных ответов несколько, вы можете вывести любой из них.
Если способа упорядочить перфокарты нужным образом не существует, выведите единственное число $-1$.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 15 | $n \le 8,ドル $m \le 100$ |
| 2 | 35 | $n \le 100,ドル $m \le 100$ |
| 3 | 50 | $n \le 100,000円,ドル $m \le 100,000円$ |
1 1 a 1 1 a
1
3 4 glhf 3 1 r 3 h 4 i 3 1 r 2 l 3 o 2 1 g 4 f
3 1 2
2 2 aa 2 1 a 2 b 2 1 b 2 a
-1