题目描述

在 Byteotia 有两棵非常高的树，而每一棵的树干上都被挖出了许多洞，高度各不相同。现在 $n$ 只可以飞得非常快的鸟决定住在这些洞里，它们中的一些互相认识因此它们想要访问认识的的鸟。鸟们飞得非常快，而且通常沿着一条直线走。为了避免在飞行中撞到别的鸟，它们决定找到某种居住的方式可以满足下面的条件：

任何的鸟都可以访问它认识的鸟，而使访问的路线不与其他鸟访问的路线相交(但是可以有同一个终点).

此外，还要使每只鸟居住的高度尽量低，保证树洞比鸟多。

我们都知道鸟的大脑很小，所以它们请你帮它们算一共有多少个方法可以满足以上条件，将答案模 $k$ 输出。

你的任务是读入鸟们的关系，计算有多少种可以使鸟安全入驻的方法，并将结果写入标准输出流。

输入格式

在标准输入流的第一行有三个整数 $n$，$m$ 和 $k$。分别表示鸟的数量，鸟的关系数和取模数（详见样例输出）。鸟的编号是 $1$ 到 $n$。接下来 $m$ 行是鸟的认识关系，第 $i+1$ 行是两个数字 $a_i$ 和 $b_i$，用一个空格隔开。每一对认识的鸟只给出一次。

输出格式

$r$ 表示满足给定约束的鸟类的不同方案数。您的程序应该在标准输出的第一行中写入一个整数 $r\bmod k$，其中 $\bmod$ 代表数学中的取模运算。如果没有方案，则输出为 0。

输入样例

3 2 10
1 2
1 3

输出样例

4

数据规模及约定

对于 $100 \%$ 的数据：

$2\le n\le 10^6$; $1 \le m\le 10^7$; $2 \le k\le 2 \times 10^6$; $1 \le a,b\le n$; $a_i \neq b_i$.