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

2085. Волшебный программист

Ограничение времени: 5.0 секунды
Ограничение памяти: 256 МБ
В одной известной уральской ИТ-компании есть множество проектов. К сожалению, во многих из них дела в разработке складываются не лучшим образом: срываются сроки, система не выдерживает нагрузку, пользователи недовольны. К счастью, в компании работает Волшебный программист Иван. Он способен прийти в проект и за короткий срок вывести разработку на принципиально другой уровень, и всё начинает работать как часы. После этого ему нет смысла оставаться в текущем проекте, и его направляют туда, где больше всего проблем.
Но у Ивана есть и свои требования: он хочет не только спасать проекты, но и изучать новые технологии. На данный момент Ивана интересуют m ещё не изученных им технологий. Иван играл в АСМ ещё в те времена, когда программе выделялся 1Мб оперативной памяти, а в отведённую секунду времени работы можно было успеть совсем немногое, поэтому он привык ценить время. Иван решил, что раз уж ему приходится путешествовать из проекта в проект, то за время работы в компании он, во-первых, должен поработать со всеми интересующими его технологиями, а во-вторых, не должен работать с одной и той же технологией в двух разных проектах — это скучно и лишило бы его столь необходимых в работе эмоций новизны. Также, разумеется, он не пойдёт в один и тот же проект дважды.
Всего в компании n проектов. В силу различных причин существует лишь n−1 пара проектов, между которыми возможен прямой переход (как в одну, так и в другую сторону). При этом из любого проекта можно попасть в любой другой посредством нескольких прямых переходов, не посещая один и тот же проект дважды, но только единственным способом. В каждом проекте используется некоторое подмножество интересующих Ивана технологий. Помогите Ивану выбрать первый проект и составить план переходов между проектами таким образом, чтобы он не возвращался в один и тот же проект дважды, а также смог ровно один раз попробовать каждую из m технологий.

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

В первой строке через пробел записаны два целых числа n и m (1 ≤ n, m ≤ 105).
Следующие n−1 строк содержат описания разрешённых прямых переходов между проектами. В j-й строке через пробел записаны два различных числа uj и vj (1 ≤ uj,vjn) — номера проектов, между которыми возможен прямой переход. Гарантируется, что заданная система переходов удовлетворяет условиям, описанным выше.
Следующие n строк описывают интересующие Ивана технологии, применяемые в каждом из проектов. i-я строка начинается с числа ai (0 ≤ aim), равного количеству применяемых интересных Ивану технологий в проекте с номером i. Затем в этой же строке через пробел записаны ai различных целых чисел от 1 до m — номера этих технологий.
Гарантируется, что сумма всех ai не превосходит 106.

Результат

Если не существует плана переходов между проектами, удовлетворяющего требованиям Ивана, выведите единственную строку «No solution» (без кавычек).
В противном случае выведите два числа s и t — номера первого и последнего проектов в подходящем плане переходов.
Если решений несколько, выведите любое.

Примеры

исходные данныерезультат
5 3
1 2
1 3
3 4
3 5
1 1
1 3
0
2 1 3
1 2
2 5
3 3
1 2
1 3
2 2 3
3 1 2 3
1 3
2 2
2 3
1 2
2 1 2
2 1 3
No solution

Замечания

Во втором примере Ивану нет смысла делать ни одного перехода, поэтому всю свою карьеру в компании он проработает в проекте 2, где и попробует все технологии. Соответственно, номера первого и последнего проектов совпадают.
Автор задачи: Александр Фетисов