Which Dreamed It

时间限制:20s      空间限制:1024MB

题目描述

有n个房间,每个房间有若干把钥匙能够打开特定房间的门。
你会做这么件事情:
最初你在房间1。
每当你到达一个房间,你可以选择该房间的一把钥匙,前往该钥匙对
应的房间,并将该钥匙丢到垃圾桶中。
你希望:最终回到房间1,且垃圾桶中有所有的钥匙。
求方案数。两组方案不同,当且仅当使用钥匙的顺序不同。注意,每
把钥匙都是不同的。


输入格式

 有多组数据。
对于每组数据第一行输入一个数n,表示房间数。
接下来n行依次描述每个房间:
首先一个数s,表示这个房间的钥匙数目,接下来s个数,分别描述每把
钥匙能够打开的房间的门。
输入以n-0结尾。


输出格式

对于每组数据,输出方案数,为了方便你的输出,请将答案对1000003取模。


样例输入

1
0
2
1 1
1 2
0

样例输出

 1
0

提示

在第一组样例中,没有钥匙,则方案数为1。
在第二组样例中,你不可能使用第二个房间的钥匙,所以方案数为0。

 
 
房间数小于等于100,钥匙数小于等于200000。
数据组数也不是特别多。


题目来源

没有写明来源

Menuappsclose