题目描述

在广袤的宇宙中，存在一个由 $n$ 个星系和 $m$ 条空间跃迁航线组成的古老星际网络，每条航线双向连接着两个不同的星系。

随着宇宙风暴的席卷，该网络遭到了严重破坏，绝大部分空间航线被迫关闭，最终只剩下了 $n-1$ 条航线。幸运的是，通过这仅存的 $n-1$ 条航线，这 $n$ 个星系依然保持着连通，即它们在拓扑结构上形成了一棵树。

星际测绘局找到了该网络被破坏前的原始设计图纸。科学家们想知道，现在残存网络中的各个星系，分别对应着原始图纸上的哪些星系。匹配规则要求：如果当前残存网络中两个星系之间存在航线直连，那么它们在原始图纸上对应的两个星系之间也必须存在航线直连。

请你计算出，满足上述规则的可能对应方式的总数量。

输入格式

第一行包含 $2$ 个正整数 $n,m$，分别表示原始网络中星系的个数和空间航线的条数。

接下来 $m$ 行，每行包含 $2$ 个正整数 $u,v$，表示在原始网络的图纸中，星系 $u$ 和星系 $v$ 之间有一条双向航线。星系从 $1$ 开始标号，保证 $u \neq v$，且每对星系之间最多只有一条航线。

接下来 $n-1$ 行，每行包含 $2$ 个正整数 $u,v$，表示当前残存的网络中，星系 $u$ 和星系 $v$ 之间仍有航线相连。保证这 $n$ 个星系通过这些航线能够保持连通。

输出格式

输出共 $1$ 行，包含一个整数，表示所有可能的星系对应方式的总数。

如果不存在任何一种可行的对应方案，则输出 0。

样例

4 3
1 2
1 3
1 4
4 1
4 2
4 3

6

样例说明

数据范围

对于 $100\%$ 的数据，$n\leq 17$，$m\leq \frac 12n(n-1)$。