Полуфинал ACM ICPC в Санкт-Петербурге — стресс даже для ветеранов
спортивного программирования. Поэтому на протяжении четырёх последних лет
программист Денис со своим наставником Вовой после соревнования
отправляются отдохнуть в любимые бары. Заходя в бар, Денис сразу заказывает
коктейль Б52. Если в карте этого коктейля нет, он ничего не пьёт. Зато
в тех местах, где Б52 готовят хорошо, Денис может повторить заказ несколько
раз.
Вова, как старший товарищ, пытается контролировать степень опьянения своего
подопечного. При входе в каждое заведение и выходе из него Вова спрашивает
у Дениса, сколько коктейлей тот выпил в последнем баре, где наливали Б52.
Если Денис не может уверенно ответить на этот вопрос, Вова понимает, что на
сегодня хватит, и отводит Дениса в гостиницу.
В этом году история повторится. Денис по опыту предыдущих четырёх
полуфиналов знает, в каких барах наливают Б52 и сколько коктейлей он выпьет
в каждом из них за один визит. Также он знает, куда они могут отправиться
после каждого из баров в их маршруте. Для каких баров Денис может заранее
заготовить правильные ответы на вопросы Вовы, какой бы маршрут они ни
выбрали?
Исходные данные
В первой строке записано целое число n — количество баров
(1 ≤ n ≤ 100 000). В следующих n строках следует описание этих баров.
В i-й из этих строк записаны целые числа ki, mi, ni1, ni2, …, nimi
(0 ≤ ki ≤ 100 000; 0 ≤ mi ≤ n). Если ki равняется нулю, то в i-м баре
не наливают Б52, а если ki положительно, то это значит, что Денис выпьет ki коктейлей
за один визит в i-й бар. ni1, ni2, …, nimi — номера баров, в которые
друзья могут пойти сразу после выхода из i-го бара (1 ≤ nij ≤ n;
nij < ni,j+1). Среди чисел nij может быть и число i. Это означает, что
друзья после выхода из i-го бара могут погулять по округе и вернуться
в этот же бар. Сумма всех чисел mi не превышает 100 000.
Бары пронумерованы в том порядке, в котором они описаны во входных данных.
Бар с номером 1 — этот тот бар, с которого Вова с Денисом начинают свой
поход. Гарантируется, что за ночь друзья могут добраться до любого
из перечисленных баров.
Результат
В
i-й из
n строк выведите, как должен отвечать Денис на вопрос Вовы при входе в
i-й
бар и при выходе из него. Каждый ответ должен иметь один из следующих форматов:
- sober — Денис ещё не выпил ни одного Б52
- X — во время последнего визита в бар, где наливали Б52, Денис выпил X коктейлей
(X — целое число от 1 до 100 000)
- unknown — при разных маршрутах до i-го бара возможны разные ситуации
Примеры
исходные данные | результат |
---|
5
0 2 2 3
6 1 4
5 2 4 5
5 1 5
0 0
| sober sober
sober 6
sober 5
unknown 5
5 5
|
2
0 2 1 2
0 2 1 2
| sober sober
sober sober
|
Автор задачи: Алексей Самсонов (подготовка — Егор Щелконогов)
Источник задачи: NEERC 2014, Четвертьфинал Восточного подрегиона