#P3659. [模板题][best定理]Which Dreamed It
[模板题][best定理]Which Dreamed It
题目描述
有 个房间。每个房间里有若干把钥匙,每把钥匙能打开某个房间的门。所有钥匙都彼此不同。
你从 号房间出发。每次从当前房间选择一把尚未使用的钥匙,前往它对应的房间,并丢弃这把钥匙。你的目标是用完所有钥匙后回到 号房间。
求满足条件的方案数。两个方案不同,当且仅当使用钥匙的顺序不同。若没有钥匙,留在 号房间算一种方案。
输入格式
输入包含多组数据,没有预先给出的数据组数。
每组数据先输入一行整数 ,表示房间数。接下来 行依次描述每个房间:每行先给出该房间的钥匙数 ,再给出 个整数,依次表示每把钥匙可以打开的房间编号。
当读到 时,输入结束。该行不对应一组数据。
输出格式
对于每组数据,输出一行一个整数,表示方案数对 取模的结果。
样例
1
0
2
1 1
1 2
0
1
0
第一组没有钥匙。第二组无法使用存放在 号房间的钥匙。
数据范围
原题给出的范围为 ,每组钥匙总数不超过 。