Cross the river#9006
Barish and Murad work as supervisors in the animal surveillance department of the Baku Zoo. Very often they have to solve tasks more difficult than those of a peasant. For example, once, using only two boats, they had to transfer all the animals of the zoo across the Kür River. Imagine yourself in their place.
There are animals in the zoo. If some animals are left unsupervised together, one of them can eat the other. For each animal, it is known which other animals can eat it. Both supervisors are experts in their field and can even handle a tiger! No animal will be able to eat another animal if there is a supervisor nearby.
The supervisors have two boats. For safety reasons, they cannot take two or more animals in the same boat. At any given time, each boat can carry at most one supervisor and one animal. At the start, all the animals and supervisors are on the left side of the river. They all need to get to the right side (clearly, the river has only two sides).
Supervisors can ride a boat across the river in any direction. The boats cannot move without supervisors. At any moment, if animals are left unsupervised on one side and they can eat each other, an unfortunate incident will occur. Obviously, this is not desirable. All animals must reach the other side of the river safely.
Your task is to determine whether this is possible.
First line contains one integer (1 \leq n \leq 200) - the number of the animals in the zoo. The animals are numbered with different numbers from to .
In each of the following lines, for each animal, a list of animals that can eat this animal is given. In the -th line for the animal with the number is given first a non-negative integer k_i - the number of animals that can eat this animal, followed by k_i various numbers - the numbers of these animals. All these numbers are in the range from to and are different from (no animal can eat itself).
The sum of all k_i is no more than .
If it's possible to move all animals to the other side of the river, print ":)", otherwise print ":(".
Beispiel 1
Beispiel 7