0235. Uncle Vasya and Bags for Potatoes

Input file name: uncle.in
Output file name: uncle.out
Time limit: 4500 ms
Memory limit: 64 megabytes

There is the storehouse in the village. At night that storehouse is guarded by guardian Uncle Vasya. There are many bags for potatoes in storehouse. All of them are closed. Every bag is unique and has his own ID from 1 to N, where N is a total number of bags. Some of bags may be inside of other bags. One bag may contain more than one bag inside. Some bags are located on the floor of storehouse. Guardian Uncle Vasya can do the following operation. This operation consists of five steps:

  1. Uncle Vasya selects some bag from the floor of storehouse and opens it.
  2. Uncle Vasya looks into opened bag and writes down on sheet of paper IDs of bags, located inside.
  3. Uncle Vasya rotates bag and all its content falls down onto floor of storehouse.
  4. Uncle Vasya takes all bags from the floor, which IDs are not written on the sheet of paper, and puts them inside the opened bag. Then he closes the bag.
  5. Uncle Vasya erases all IDs from sheet of paper and puts bag onto floor.
Given initial relations of all bags, you need to calculate total number of possible combinations of bags which can be reached by multiple applying of operation described above.

Input file

There is number N on the first line of input file – the total number of bags in storehouse (1 ≤ N ≤ 18). Next N lines contain descriptions of bags. I-th line describes I-th bag. Description of bag starts with number Ci – number of bags which are immediately inside of I-th bag, then Ci numbers follow – numbers of bags which are immediately inside of I-th bag. Bags form tree-like structure and can not be cyclically inside each other.

Output file

On first line of output file must be only one integer – total number of possible combinations of bags, reachable by iterating described operation. It is guaranteed that the answer is less than 1050.

Examples:

uncle.inuncle.out
2 1 2 0 3
2 0 0 3

Note:

Picture for example 1 (combinations, that can be reached (starting √ first)): First step is applying described operation to bag #1, second is applying operation to bag #2.


Source: Petrozavodsk Winter 2004. SPb ETU Contest, Sunday, February 01

Discuss       Submit a solution



Printable version