题目描述

夏洛克·福尔摩斯在调查一宗犯罪事件时，发现了一定数量的线索，而且他还发现有些线索存在直接关系。线索之间的直接关系是相互的，即 A -> B，并且 B -> A。两条线索直接关系不超过一条。
当然，夏洛克·福尔摩斯能找出所有线索的直接关系，但是这将花费太多的时间，到时罪犯已经隐藏起来了。为了更快的抓住犯罪分子，夏洛克·福尔摩斯需要知道每条线索之间的关系（可以是直接关系也可以是间接关系）。
夏洛克·福尔摩斯发现自己最少需要找到额外的 T 组直接关系就可以抓住罪犯。请你帮他数一数有多少种方式可以找到正确的线索之间的直接关系。由于方法数比较多，结果模 k。

输入格式

第一行三个整数 n, m, k，表示 n 条线索，m 对直接关系，模 k。
接下来 m 行，每行两个整数 a, b，表示 a 和 b 有直接关系。
这是线索之间的直接联系。保证任何两条线索都由一个直接连接联系在一起。请注意，线索之间的直接联系是相互的。

输出格式

输出方案数。

样例1

输入

2 0 1000000000

输出

1

样例2

输入

3 0 100

输出

3

样例3

输入

4 1 10000000
1 4

输出

8

数据范围

对于 30%的数据，1 \(\leq\) n \(\leq\) 20, 0 \(\leq\) m \(\leq\) 20, 1 \(\leq\) k \(\leq\) \(10^9\), 1 \(\leq\) a, b \(\leq\) n, a ≠ b；
对于 100%的数据，1 \(\leq\) n \(\leq\) \(10^5\), 0 \(\leq\) m \(\leq\) \(10^5\), 1 \(\leq\) k \(\leq\) \(10^9\), 1 \(\leq\) a, b \(\leq\) n, a ≠ b。

限制

1s

样例解释

样例 1：只有两条线索，并且线索之间没有之间关系，所以只有一种方案。
样例 2：有三条线索，有三种方案，1 -> 2, 2 -> 3、1 -> 3, 2->3、1 -> 2, 1 -> 3。
样例 3：方案太多，自己数。

来源

Codeforces156D
CWOI新高二专题测试十六