暂无测试数据。

你有很多颜料，还有一棵树。因此你打算给树上色。

---

定义 $g$ 为下面这个问题的答案：

对于一棵 $n$ 个节点的树，最开始边全为黑色，现选择一些边染成红色，一种合法的染色方案当且仅当任意一点到 $1$ 的简单路径上有至少一条红边，则 $g$ 表示合法染色方案数量。

先给定一棵 $n$ 个节点的树，很不巧，小 C 只记住了其中 $m$ 条边，现在此基础上补全剩余的 $n-1-m$ 条边，使得 $(g\bmod p)$ 最大，其中 $p$ 是给定的数。

请注意：你需要最大化 $(g \bmod p)$ 而非 g。

考虑到 ccf 一般不配置 SPJ，因此你不需要输出方案。

输入格式

第一行一个正整数 $n,m,p$。

接下来 $m$ 行，每行两个整数 $(u,v)$，描述已知树上的边。

变量含义如题所示，保证存在至少一棵合法的树使得同时拥有这 $m$ 条边。

输出格式

一行一个正整数，表示答案。

数据范围

• 对于 $50\%$ 的数据，$m=n-1,p=998244353$。

• 对于另外 $50\%$ 的数据，没有特殊限制。

• 对于 $100\%$ 的数据，$1\le n\leq 10^6,0\le m<n,1\le p\leq 10^9$。

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