P3427 [POI 2005] DZI-Hollows

# Description There are two very tall trees in Byteotia, and many hollows have been carved into their trunks at different heights. Now $n$ very fast birds have decided to live in these hollows. Some birds know each other, so they want to visit the birds they know. The birds fly very fast, and they usually fly in straight lines. To avoid colliding in flight, they decide to choose a way to live that satisfies the following condition: - Every bird can visit each bird it knows, and the visiting routes do not intersect with the visiting routes of other birds (they may share endpoints). In addition, we want each bird to live as low as possible in height, and it is guaranteed that there are more hollows than birds. We all know that birds have small brains, so they ask you to count how many ways satisfy the above conditions and output the answer modulo $k$.

在 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$。每一对认识的鸟只给出一次。

Let $r$ be the number of different arrangements of the birds that satisfy the given constraints. Your program should print a single integer $r \bmod k$ on the first line of the standard output. If there is no valid arrangement, the correct output is $0$.

Translated by ChatGPT 5