题目描述

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

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

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

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

输入格式

在标准输入流的第一行有三个整数 $n，m$ 和 $k$，分别表示鸟的数量，鸟的关系数取模数（$2\le n\le 1000000,1\le m\le 10000000,2\le k\le 2000000$）。鸟的编号是 $1$ 到 $n$。

接下来 $m$ 行是鸟的认识关系，第 $i+1$ 行是两个数字 $a_i$和 $b_i$，用一个空格隔开。$1\le a,b\le n,a_i\ne b_i$。每一对认识的鸟只给出一次。

输出格式

设 $r$ 表示满足给定约束的鸟类的不同方案数。您的程序应该在标准输出的第一行中输出一个整数 $r\bmod k$。如果没有方案，则正确的结果为 $0$。

3 2 10
1 2
1 3

4