ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

NEERC 2014, Четвертьфинал Восточного подрегиона

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

B. Не взбалтывать и не смешивать

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Полуфинал ACM ICPC в Санкт-Петербурге — стресс даже для ветеранов спортивного программирования. Поэтому на протяжении четырёх последних лет программист Денис со своим наставником Вовой после соревнования отправляются отдохнуть в любимые бары. Заходя в бар, Денис сразу заказывает коктейль Б52. Если в карте этого коктейля нет, он ничего не пьёт. Зато в тех местах, где Б52 готовят хорошо, Денис может повторить заказ несколько раз.
Вова, как старший товарищ, пытается контролировать степень опьянения своего подопечного. При входе в каждое заведение и выходе из него Вова спрашивает у Дениса, сколько коктейлей тот выпил в последнем баре, где наливали Б52. Если Денис не может уверенно ответить на этот вопрос, Вова понимает, что на сегодня хватит, и отводит Дениса в гостиницу.
В этом году история повторится. Денис по опыту предыдущих четырёх полуфиналов знает, в каких барах наливают Б52 и сколько коктейлей он выпьет в каждом из них за один визит. Также он знает, куда они могут отправиться после каждого из баров в их маршруте. Для каких баров Денис может заранее заготовить правильные ответы на вопросы Вовы, какой бы маршрут они ни выбрали?

Исходные данные

В первой строке записано целое число n — количество баров (1 ≤ n ≤ 100 000). В следующих n строках следует описание этих баров. В i-й из этих строк записаны целые числа ki, mi, ni1, ni2, …, nimi (0 ≤ ki ≤ 100 000; 0 ≤ min). Если ki равняется нулю, то в i-м баре не наливают Б52, а если ki положительно, то это значит, что Денис выпьет ki коктейлей за один визит в i-й бар. ni1, ni2, …, nimi — номера баров, в которые друзья могут пойти сразу после выхода из i-го бара (1 ≤ nijn; 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, Четвертьфинал Восточного подрегиона
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 2013. Не взбалтывать и не смешивать