favorite We need a little bit of your help to keep things running, click on this banner to learn more

Shortest paths - interesting graph problems

Cross the river


Barysh and Murad work as supervisors in the animal surveillance department of the Baku Zoo. Very often they have to solve tasks more difficult than the tasks of the peasant. For example, once, using only two boats, they had to transfer all the animals of the zoo across the Kura River. Imagine yourself in their place.

There are n animals in the zoo. If some animals are left unattended together, one of them can eat the other. For each animal, it is known what other animals can eat it. Both supervisors are masters of their craft and can even cope with a tiger! Any animal will not be able to eat another animal if there is an overseer nearby.

Overseers have two boats. For safety reasons, you cannot take two or more animals into the boat. In each of the boats at the same time there can be at most one overseer and one animal. At the very beginning, all animals and overseers are on the left side of the river. They all need to go to the right side (obviously, the river has only two sides).

Overseers can swim across the river in any direction. Boats cannot move without overseers. At any moment, if animals are left unattended on one side and can eat each other, an accident will occur. Naturally, this is not permissible. All animals must go to the other side of the river safe and sound.

You are required to find out if this is possible.


First line contains one integer n (1n200) - the number of the animals in the zoo.The animals are numbered with different numbers from 1 to n.

In each of the following n lines, for each animal, a list of animals that can eat this animal is given. In the i - th line for the animal with the number i is given first a non-negative integer ki - the number of animals that can eat this animal, followed by ki various numbers - the numbers of these animals. All these numbers are in the range from 1 to n and are different from i (no animal can eat itself).

The sum of all ki is no more than 1500.


If its possible to move all animals to the other side of the river, print ":)", otherwise print ":(".

Time limit 1 second
Memory limit 128 MiB
Input example #1
3 3 2 4
1 1
1 1
1 1
Output example #1
Input example #7
4 2 5 3 4
4 3 1 4 5
4 1 5 2 4
4 1 5 3 2
4 4 2 1 3
Output example #7
Author Rashad Mammadov
Source 2019 Azərbaycan Milli İnformatika Olimpiada, Final, May 5