#P18564. Not Another Constructive Problem
Not Another Constructive Problem
Not Another Constructive Problem
考虑一棵有 个顶点的树 ,顶点编号为 。顶点 最初放着数值 ,其中 是 到 的一个排列。
你需要执行以下操作恰好 次:
- 选择一条仍在 中的边 。
- 交换顶点 上的数值,即交换 。
- 从 中删除这条边。
最后,树的所有边都会被删除。如果存在一种执行这些操作的方法,使得最终每个顶点 上的数值都等于 ,就称树 为 yummy。
你也许以为小青鱼想让你找出一个方案来证明某棵树是 yummy。但这场比赛的构造题已经太多了!因此,他给你一个有 个顶点、拥有许多许多边的无向图 。具体来说,顶点 之间有 条彼此不同的边。
请计算 中有多少棵 yummy 生成树。两棵生成树不同,当且仅当它们包含的边的集合不同。答案可能很大,请输出答案对 取模的结果。
输入格式
输入只包含一组数据。
第一行包含一个整数 (),表示顶点数。
第二行包含一个排列 ,表示每个顶点最初的数值。
第三行包含一个排列 ,表示每个顶点最终需要达到的数值。
接下来 行描述矩阵 ,每行包含 个整数。第 行第 个整数为 (),表示顶点 之间的边数。
保证对所有 ,都有 且 。 均为 到 的排列。
输出格式
输出一行一个整数,表示 yummy 生成树数量对 取模的结果。
原样例 1
4
1 2 3 4
3 4 2 1
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
12
原样例 2
6
1 2 3 4 5 6
5 3 4 1 6 2
0 3 3 2 1 2
3 0 2 2 2 1
3 2 0 3 2 3
2 2 3 0 1 2
1 2 2 1 0 1
2 1 3 2 1 0
5050