Пройти через реку
Барыш и Мурад работают надсмотрщиками в отделе надсмотра за животными Бакинского зоопарка. Очень часто им приходится решать задачи сложнее задачи крестьянина. Например, однажды, использую только две лодки они должны были перевести всех животных зоопарка через реку Кура. Представьте себя на их месте.
В зоопарке имеются n животных. Если оставить некоторых животных вместе без присмотра, то один из них может съесть другого. Для каждого животного известно каких других животных он может съесть. Оба надсмотрщика мастера своего дела и могут справиться даже с тигром! Любое животное не сможет съесть другое животное, если рядом находится надсмотрщик.
У надсмотрщиков имеются две лодки. По правилам безопасности, нельзя брать в лодку двух или более животных. В каждой из лодок одновременно могут находиться самое большее один надсмотрщик и одно животное. В самом начале все животные и надсмотрщики находятся по левую сторону реки. Им всем надо перейти на правую сторону. (Очевидно, что у реки имеются только две стороны)
Надсмотрщики могут переплывать через реку в любом направлении. Лодки не могут двигаться без надсмотрщиков. В любой момент если на одной из сторон останутся животные без присмотра которые могут съесть друг друга, то произойдет несчастный случай. Естественно, это не допустимо. Все животные должны перейти на другую сторону реки целыми и невредимыми.
От вас требуется выяснить, возможно ли это.
Входные данные
В первой строке дано одно целое число n (1 ≤ n ≤ 200) - количество животных в зоопарке. Животные пронумерованы различными числами от 1 до n.
В каждой из последующих n строк, для каждого животного, дан список животных которые могут съесть это животное. В i-той строке для животного с номером i дается сначала неотрицательное целое число k[i] - количество животных, которые могут съесть это животное, далее следуют k[i] различных чисел – номера этих животных. Все эти числа находятся в промежутке от 1 до n и отличны от i (никакое животное не может съесть самого себя).
Сумма всех k[i] не больше 1500.
Выходные данные
Если возможно перевести всех животных на другую сторону реки, выведите ":)", в противном случае выведите ":(".