usst 小学里有 名学生，他们分别居住在 个地点，第 名学生居住在第 个地点，这些地点由 条双向道路连接，保证任意两个地点之间可以通过若干条双向道路抵达。学校则位于另外的第 个地点，第 个地点与第 个地点之间有另外一条双向道路链接。

最近学校开始启用校车来接学生上学，每一辆校车上都可以坐无限个学生，且每辆校车在一天内不会重复经过一条道路，校车终点始终为学校。每一位学生一天内只能乘坐一辆校车，且只能在自己居住的节点处上车，在学校下车。为了节省资金，学校会在保证每位学生都能坐上校车的前提下，安排最少数量的校车，每天早上从某些地点出发，并经过若干道路和地点最终抵达学校。第 位学生可以自由选择一辆经过第 个地点的校车，搭乘它到达学校。

现在学校想要从 个学生中选出 人参加某个比赛，但是学校不希望这 人之间太过 “熟悉”，请问一共有多少种不同的选人方案。

如果一种选择方案中， 个人可能在同一天里乘坐上同一辆校车，那就称这 个人之间太过 “熟悉”。

对于任意两个方案，如果存在一名学生在一个方案中且不在另一个方案中，那么就认为这两种方案不同。

输入第  行包含  个正整数  ，代表学生数量和学生居住的地点数量。()

接下来  行每行有  个正整数  ，代表第  个地点与第  个地点之间有一条双向道路。（）

输出一行，一个整数，代表选人方案数量。

5
1 2
2 3
3 4
4 5

0

5
1 2
2 3
2 4
1 5

8

对于第二组样例，校车会从第  个地点出发，前往学校。合法的选人方案有 {}, {}, {}, {}, {}, {}, {}, {}