← 返回题目列表

Codeforces · 156/D

D. 线索

中文机器翻译题面 查看原题

当福尔摩斯调查另一起犯罪案件时,他发现了一定数量的线索。此外,他已经发现了其中一些线索之间的直接联系。线索之间的直接联系是相互的。也就是说,线索A和B之间的直接联系和线索B和A之间的直接联系是同一件事。两条线索之间最多只能存在一个直接联系。

Sherlock当然能够找到所有线索之间的直接联系。但这会花费太多时间,犯罪分子可以利用这些额外的时间来隐藏。为了侦破犯罪,夏洛克需要将每条线索与所有其他线索联系起来(也许不是直接联系,而是通过一些其他线索联系起来)。如果线索 A 和 B 之间存在直接链接,或者 A 与链接到 B 的其他线索 C 之间存在直接链接,则线索 A 和 B 被视为链接。

夏洛克·福尔摩斯计算了他需要找到的破案所需的最少额外直接链接数量。事实证明,它等于 T。

请数数不同的方式,准确找到T条线索之间的直接联系,从而最终破案。如果存在两条线索,其中一种方式具有直接链接而另一种方式不具有直接链接,则认为寻找直接链接的两种方式是不同的。

由于不同方式的数量可能会相当大,因此将其以 k 为模进行打印。

输入

第一行包含三个空格分隔的整数 n、m、k (1 ≤ n ≤ 105, 0 ≤ m ≤ 105, 1 ≤ k ≤ 109) — 线索数、Holmes 已经找到的直接线索链接数以及取模运算的除数。

接下来的 m 行中的每一行都包含两个整数 a 和 b (1 ≤ a, b ≤ n, a ≠ b),表示线索之间的直接联系。保证任意两条线索之间的直接链接不超过一个。请注意,线索之间的直接联系是相互的。

输出

打印单个数字——对 k 取模的问题的答案。

示例

输入 #1

2 0 1000000000

输出 #1

1

输入 #2

3 0 100

输出 #2

3

输入 #3

4 1 1000000000
1 4

输出 #3

8

注意

第一个样本只有两条线索,Sherlock还没有发现它们之间有任何直接联系。破案的唯一方法就是找到联系。

第二个样本有3条线索,Sherlock还没有发现它们之间有任何直接联系。他必须找到线索之间三个可能的直接联系中的两个来破案——有 3 种方法可以做到这一点。

第三个样本有四个线索,侦探已经找到了第一个和第四个线索之间的直接联系。有8种方法可以找到两条剩余的线索来破案。