238. Uncle Vasya and Bags for Potatoes
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.
Input
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. Ith line describes Ith bag. Description of bag starts with number Ci  number of bags which are immediately inside of Ith bag, then Ci numbers follow  numbers of bags which are immediately inside of Ith bag. Bags form treelike structure and can not be cyclically inside each other.
Output
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.
Sample test(s)
Input
Test #1
2
1 2
0
Test #2
2
0
0
Output
Test #1
3
Test #2
3
Author:  

Resource:  Folklore

Date:  

Server time: 20171120 23:47:23  Online Contester Team © 2002  2016. All rights reserved. 

