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 n 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.

Input

First line contains one integer n (1 ≤ n ≤ 200) - 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.

Output

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