#P4455. [Zjoi2016]小星星
[Zjoi2016]小星星
题目描述
小 Y 做了一件由 颗小星星和 条彩色细线组成的饰品,每条细线连接两颗小星星。有一天,饰品上的许多细线被拆掉了,只剩下 条线,但这 颗小星星仍然连通,形成了一棵树。
小 Y 找到了饰品原来的设计图。她想把现在的 颗小星星和图纸上的 颗小星星一一对应。若现在的两颗小星星有细线相连,它们对应的图纸上的两颗小星星也必须有细线相连。请计算有多少种满足条件的对应方式。
输入格式
第一行输入两个正整数 ,分别表示原饰品的小星星数和细线数。两套编号均为 到 。
接下来 行,每行输入两个正整数 ,表示原饰品上连接 和 的一条细线。保证 ,且每对小星星之间最多只有一条细线。
接下来 行,每行输入两个正整数 ,表示现有饰品上的一条细线。保证现有饰品是连通的。
输出格式
输出一行一个整数,表示有效对应方式的数量。如果不存在有效的对应方式,输出 0。
样例 1
4 3
1 2
1 3
1 4
4 1
4 2
4 3
6
样例 1 说明
现有饰品的第 颗小星星必须对应原图纸的第 颗。现在的第 颗可按任意顺序对应原图纸的第 颗,共有 种方式。
样例 2
10 23
3 4
10 1
1 2
3 2
5 3
9 6
7 1
8 4
10 2
6 5
5 9
7 3
9 3
7 8
8 9
4 7
8 10
9 1
8 5
6 8
8 2
9 10
3 6
4 3
5 4
1 2
10 9
6 2
1 3
8 5
2 9
7 6
2968
数据规模与约定
,。
| 测试点 | 特殊约定 | |
|---|---|---|
| 无 | ||
| 现有饰品中每颗小星星至多与另外两颗小星星相连 | ||
| 无 | ||
| 答案不超过 | ||
| 无 | ||