В одной известной уральской ИТ-компании есть множество проектов. К сожалению, во многих из них дела в разработке складываются не лучшим образом: срываются сроки, система не выдерживает нагрузку, пользователи недовольны. К счастью, в компании работает Волшебный программист Иван. Он способен прийти в проект и за короткий срок вывести разработку на принципиально другой уровень, и всё начинает работать как часы. После этого ему нет смысла оставаться в текущем проекте, и его направляют туда, где больше всего проблем.

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

Всего в компании n проектов. В силу различных причин существует лишь n−1 пара проектов, между которыми возможен прямой переход (как в одну, так и в другую сторону). При этом из любого проекта можно попасть в любой другой посредством нескольких прямых переходов, не посещая один и тот же проект дважды, но только единственным способом. В каждом проекте используется некоторое подмножество интересующих Ивана технологий. Помогите Ивану выбрать первый проект и составить план переходов между проектами таким образом, чтобы он не возвращался в один и тот же проект дважды, а также смог ровно один раз попробовать каждую из m технологий.

В первой строке через пробел записаны два целых числа n и m (1 ≤ n, m ≤ 10⁵).

Следующие n−1 строк содержат описания разрешённых прямых переходов между проектами. В j-й строке через пробел записаны два различных числа u_j и v_j (1 ≤ u_j,v_j ≤ n) — номера проектов, между которыми возможен прямой переход. Гарантируется, что заданная система переходов удовлетворяет условиям, описанным выше.

Следующие n строк описывают интересующие Ивана технологии, применяемые в каждом из проектов. i-я строка начинается с числа a_i (0 ≤ a_i ≤ m), равного количеству применяемых интересных Ивану технологий в проекте с номером i. Затем в этой же строке через пробел записаны a_i различных целых чисел от 1 до m — номера этих технологий.

Гарантируется, что сумма всех a_i не превосходит 10⁶.

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

В противном случае выведите два числа s и t — номера первого и последнего проектов в подходящем плане переходов.

Если решений несколько, выведите любое.

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