0 人解决，1 人已尝试。
0 份提交通过，共有 1 份提交。
9.9 EMB 奖励。
1402. Hollows
单点时限: 2.0 sec
内存限制: 256 MB
There are two extremely high trees in Byteotia, and each of them has many hollows scooped out in its trunk, one under another. Once upon a time n very fast birds decided to inhabit the hollows. Some of them know each other and therefore would like to be able to pay one another visits in their hollows. The birds fly very fast and always along a straight line. In order to avoid the danger of collision they decided to quarter in a way that:
each two birds that would like to pay themselves visits live in different trees, and
for each two pairs of familiar birds, the segments connecting the hollows of the familiar birds do not intersect (they may, however, have a common endpoint).
In addition, the birds would like to live as low as possible. So in each tree they inhabit a certain number of lower hollows. There are more hollows in each tree than there are birds in whole.
It is well-known that birds have very small brains. That’s why they have asked you – a respected ornithologist – to help them find out in how many ways they can quarter in the hollows.
Task
Write a programme that:
reads from the standard input the description of acquaintanceship between the birds,
calculates in how many ways can the birds be quartered in the trees, satisfying the above constraints,
writes the result to the standard output.
输入格式
In the first line of the standard input there are three integers written n, m and k, denoting respectively: the number of birds, the number of distinct pairs of birds knowing each other and the number that is to be used when giving result (see: Output), 2 <= n <= 1 000 000, 1 <= m <= 10 000 000, 2 <= k <= 2 000 000. The birds are numbered from 1 to n. In the following m lines the pairs of birds knowing each other are given, one per line. In the line no. i + 1 two integers ai and bi, separated by a single space, are written (1 <= ai, bi <= n, ai <> bi). These are the numbers of the familiar birds. Each (unordered) pair of familiar birds is given exactly once.
输出格式
Let r denote the number of distinct quarterings of birds satysfying the given constraints. Your programme should write one integer in the first line of the standard output: the remainder of division of r by k. If no quartering exists the correst result is 0.
样例
Input
3 2 10 1 2 1 3
Output
4
题目标签