题目描述

在幻境深处盘踞着一股被称为「暗之锁链」的神秘力量，它是人们心底阴影的凝聚，历代挑战者都想将它彻底击溃。

经过长期观察，你发现暗之锁链呈现一张无向图的结构：图中有 $N$ 个节点，边分为两类——骨架边与寄生边。

骨架边共有 $N-1$ 条，且任意两个节点之间都存在一条仅由骨架边构成的路径（换言之，全部骨架边恰好构成一棵树）。寄生边则有 $M$ 条。

你的目标是把这张网斩成互不相通的两部分，但战斗规则十分苛刻：

• 一开始所有寄生边都处于无敌状态，你第一剑只能砍断一条骨架边；
• 一旦某条骨架边被砍断，暗之锁链立刻转入防御姿态：余下的骨架边全部变为无敌，而寄生边的无敌效果消失；
• 你只剩下再砍断一条寄生边的力气。

你想知道，一共有多少种出剑方案可以最终将它击溃。

注意：即使你砍断某条骨架边之后，整张网已经断成了两截，你也必须再砍断一条寄生边，才算真正击败了它。

输入格式

第一行包含两个整数 $N$ 和 $M$。

接下来 $N-1$ 行，每行两个整数 $A$、$B$，表示节点 $A$ 与节点 $B$ 之间有一条骨架边。

再接下来 $M$ 行，以同样的格式给出每条寄生边。

输出格式

输出一个整数，表示可以击溃暗之锁链的方案总数。

样例

4 1
1 2
2 3
1 4
3 4

3

提示

对于全部数据，$1\le N \le 100000$，$1\le M \le 200000$，且保证答案不超过 $2^{31}-1$。