你有很多颜料，还有一棵树。因此你打算给树上色。
定义 g 为下面这个问题的答案：
对于一棵 n 个节点的树，最开始边全为黑色，现选择一些边染成红色，一种合法的染色方案当且仅当任意一点到 1 的简单路径上有至少一条红边，则 g 表示合法染色方案数量。
先给定一棵 n 个节点的树，很不巧，小 C 只记住了其中 m 条边，现在此基础上补全剩余的 n−1−m 条边，使得 (g mod p) 最大，其中 p 是给定的数。
请注意：你需要最大化 (g mod p) 而非 g。
第一行一个正整数 n,m,p。
接下来 m 行，每行两个整数 (u,v)，描述已知树上的边。
变量含义如题所示，保证存在至少一棵合法的树使得同时拥有这 m 条边。
一行一个正整数，表示答案。
3 2 1000 1 2 1 3
1
10000 10 1024 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11
512
对于 50% 的数据，m=n−1,p=998244353。
对于另外 50% 的数据，没有特殊限制。
对于 100% 的数据， 1≤n≤10^6,0≤m<n,1≤p≤10^9 。
样例解释1
你获得了一棵完整的树。
为了满足题目的限制，你必须把两条边都染成红色。
因此只有一种方法。
样例解释2
我想到了一个绝妙的样例解释，可惜字数限制太少我写不下::>_<::
大家自己思考为什么答案是这个吧！