历史上，盒先生曾经在一场比赛中连着出了三道数数题。由于众多选手参与了那场比赛且这三道数数题都是简单题的定位，这场比赛被选手们狠狠羞辱了。
现在，为了纪念那个时刻，盒先生又出了一个数数题给你做。
定义一张无向图 为星图，当且仅当图 是树（即无重边无环的无向连通图），且图 包含边数最多的简单路径恰好包含 条边。注意，仅包含两个点一条边的无向图不是星图。
定义星图 的根 为星图 中唯一一个度数大于 的点。
现在，给定一张 个点 条边无重边无自环的无向图 ，你需要找到一组 的星子图，使得 中的每个点作为其中最多一张星子图的根，且 中的每条边恰好出现在其中一张星子图中，并计算这样的星子图组的方案数。形式化的，你需要计算集合 的方案数，使得：
1. 对于任意 ， 是 的子图。
2. 对于任意 ， 是星图。
3. 不存在 且 ，使得 。
4. 对于任意 中的边 ，存在 ，满足 并且对于任意 有 。
特别的，若 ，即某方案不包含任何星子图也合法，也算一种方案。
由于答案可能会很大，你只需要输出答案对 取模后的结果。
注意，两个星子图 和 不同，可以是点集不同，也可以是边集不同，我们以有标号无向图的视角看待它们。

第一行两个整数  ，表示无向图的点数和边数。
接下来  行，每行两个整数  ，表示无向图中有一条连接点  和点  的边，保证无重边。

输出一行一个整数表示答案对  取模后的结果。

4 4
1 2
2 3
3 4
4 1

2