Перейти через річку
Бариш і Мурад працюють наглядачами у відділі нагляду за тваринами Бакинського зоопарку. Часто їм доводиться вирішувати завдання складніші за завдання селянина. Наприклад, одного разу, використовуючи лише два човни, вони повинні були перевезти всіх тварин зоопарку через річку Кура. Уявіть себе на їхньому місці.
У зоопарку є n тварин. Якщо залишити деяких тварин разом без нагляду, то один з них може з'їсти іншого. Для кожної тварини відомо, яких інших тварин вона може з'їсти. Обидва наглядачі майстри своєї справи і можуть впоратися навіть з тигром! Жодна тварина не зможе з'їсти іншу тварину, якщо поруч знаходиться наглядач.
У наглядачів є два човни. За правилами безпеки, не можна брати в човен двох або більше тварин. У кожному з човнів одночасно можуть знаходитися щонайбільше один наглядач і одна тварина. На самому початку всі тварини і наглядачі знаходяться по ліву сторону річки. Їм усім треба перейти на праву сторону. (Очевидно, що у річки є лише дві сторони)
Наглядачі можуть перепливати через річку в будь-якому напрямку. Човни не можуть рухатися без наглядачів. У будь-який момент, якщо на одній зі сторін залишаться тварини без нагляду, які можуть з'їсти одна одну, то станеться нещасний випадок. Звісно, це не допустимо. Всі тварини повинні перейти на іншу сторону річки цілими і неушкодженими.
Від вас вимагається з'ясувати, чи можливо це.
Вхідні дані
У першому рядку дано одне ціле число n (1 ≤ n ≤ 200) - кількість тварин у зоопарку. Тварини пронумеровані різними числами від 1 до n.
У кожному з наступних n рядків, для кожної тварини, дано список тварин, які можуть з'їсти цю тварину. У i-му рядку для тварини з номером i дається спочатку невід'ємне ціле число k[i] - кількість тварин, які можуть з'їсти цю тварину, далі слідують k[i] різних чисел – номери цих тварин. Всі ці числа знаходяться в проміжку від 1 до n і відмінні від i (жодна тварина не може з'їсти саму себе).
Сума всіх k[i] не більше 1500.
Вихідні дані
Якщо можливо перевести всіх тварин на іншу сторону річки, виведіть ":)", в іншому випадку виведіть ":(".