题目描述

当夏洛克·福尔摩斯调查另一起案件时，他发现了若干线索。同时，他已经找到了某些线索之间的直接链接。线索间的直接链接是相互的，即线索 $A$ 与 $B$ 之间的直接链接和线索 $B$ 与 $A$ 之间的直接链接是同一回事。任意两条线索之间最多存在一个直接链接。

当然，夏洛克能够找出所有线索之间的直接链接。但这会耗费太多时间，犯罪分子可能利用这段额外时间藏匿。要破解案件，夏洛克需要确保每条线索都与其他所有线索相连（不一定直接相连，可以通过其他线索间接连接）。线索 $A$ 和 $B$ 被视为相连的条件是：要么存在直接链接，要么存在线索 $A$ 与某个其他线索 $C$ 的直接链接，且线索 $C$ 与 $B$ 相连。

夏洛克·福尔摩斯计算出了破解案件所需寻找的最少额外直接链接数量，结果为 $T$。

请计算有多少种不同的方法可以恰好找出 $T$ 条线索间的直接链接，使得案件最终能够破解。如果两种方法中存在某两条线索在一种方法中有直接链接而在另一种方法中没有，则视为不同的方法。

由于不同的方法数可能非常大，请输出对 $k$ 取模后的结果。

输入格式

第一行包含三个以空格分隔的整数 $n, m, k$（$1≤n≤10^5$，$0≤m≤10^5$，$1≤k≤10^9$）——分别表示线索数量、福尔摩斯已找到的直接链接数量以及模运算的除数。

接下来 $m$ 行每行包含两个整数 $a$ 和 $b$（$1≤a, b≤n$，$a≠b$），表示一条直接链接。保证任意两条线索之间最多只有一个直接链接。注意线索间的直接链接是相互的。

输出格式

输出单个数字——表示对 $k$ 取模后的问题答案。

样例

2 0 1000000000

1

3 0 100

3

4 1 1000000000
1 4

8

提示

样例解释

第一个样例中只有两条线索，夏洛克尚未发现它们之间的任何直接链接。破解案件的唯一方法就是找出这条链接。

第二个样例中有三条线索，夏洛克尚未发现它们之间的任何直接链接。他需要找出三条可能直接链接中的两条来破解案件——实现这一目标共有 $3$ 种方法。

第三个样例中有四条线索，侦探已经发现了第一条与第四条线索之间的直接链接。找出剩余两条线索以破解案件共有 $8$ 种方法。