[POI2005] DZI-Hollows

题目描述

在 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$。

输入输出样例

输入样例 #1

3 2 10
1 2
1 3

输出样例 #1

4