time limit per test: 0.25 sec. memory limit per test: 12228 KB
input: standard output: standard
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.
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.
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 10^50.
Test #1 2 1 2 0
Test #2 2 0 0
Test #1 3
Test #2 3
Codeforces (c) Copyright 2010-2021 Mike Mirzayanov