Polish version    English version  
  History of OI

 About Olympic
 History of OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 OI books
 National team
 Olympic camps
 Photo gallery

Task: Hollows

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.


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.


For the following input data:
3 2 10
1 2
1 3
the correct answer is:

Print friendly version