#P17742. 小A的森林
小A的森林
题目描述
小A通过魔法阵吸收到大量魔力,拥有了强大的实力,于是他准备去探险。
小A来到了一片古老的森林,他发现在这片森林中的很多地方,人们会失去方向感,从而迷失。小A仔细研究了这片森林的灵脉,灵脉是一张无向无环联通图。通过进一步的研究,小A还了解到这片森林的灵脉曾经被施加过迷失诅咒。诅咒是一条被污染的灵脉,森林的灵脉被施加过诅咒后,如果有一个子联通块和被污染的灵脉产生共鸣,这个地方的诅咒就会十分明显,使人迷失。
产生共鸣是指两条灵脉同构。具体来说,如果用一个边集来描绘一个灵脉,那么假设一条灵脉为,另一条为。两条灵脉能产生共鸣,当且仅当且存在一个排列,使得。
为了解除诅咒,小A希望了解森林的灵脉中,有多少子联通块会和被污染的灵脉产生共鸣。
因为答案太大了,小A希望你告诉他答案对P取模的结果。
输入格式
从标准输入读入。
第一行一个正整数,表示森林灵脉的节点个数。
接下来行,每行两个整数,表示之间有连边。
然后一行一个正整数,表示被污染的灵脉的节点个数。
接下来行,每行两个整数,表示之间有连边。
最后一个正整数,表示对取模。
输出格式
输出到标准输出。
一行一个整数,表示答案对P取模的结果。
样例
样例输入 1
5
1 2
2 3
3 4
4 5
3
1 3
2 3
998244353
样例输出 1
3
样例解释
有3条灵脉会产生共鸣:(1,2,3),(2,3,4),(3,4,5)。
数据范围
subtask 1 13pts
subtask 2 11pts
subtask 3 19pts 被污染的灵脉树型为一条链。
subtask 4 12pts 被污染的灵脉树型为一个菊花。
subtask 5 17pts ,是质数。
subtask 6 9pts ,是质数。
subtask 7 11pts
subtask 8 8pts 无特殊限制。
本次核对PDF:task.pdf,第6–7页。
原题面:task.md。