Description

There are $N$ women and $N$ men in the app’s backend, and each of them hopes to find a suitable partner. For convenience, each man is assigned a unique ID from $1$ to $N$. Each woman is also assigned a unique ID in the same way.

The biggest feature of JYY’s app is that it gives women more power of choice, allowing each woman to specify her own “preferred men list”. Each woman’s preferred men list is a subset of all men, and it may be empty. If the list is non-empty, she will choose one man from it as the one she finally accepts.

JYY uses the following algorithm to quickly match a man for each woman to finally accept: the men in the preferred men list are shown to her in increasing order of their IDs. Each time a man is shown, she independently accepts him with probability $P$ (that is, rejects him with probability $1-P$). If she rejects, the app shows the next man in the list, and so on. If all men in the list have been shown, the agency will show these men again in the same order, repeatedly, until she accepts some man. Obviously, under this rule, each woman can accept only one man, while a man may be accepted by multiple women. Of course, it is also possible that some men are not accepted by any woman.

In this way, each woman gets the man she accepts (except those whose preferred men list is empty). Now consider any two different women $a$ and $b$ whose preferred men lists are non-empty. If the ID of $a$ is smaller than the ID of $b$, but the ID of the man chosen by $a$ is larger than the ID of the man chosen by $b$, then women $a$ and $b$ are called an unstable pair.

Since each woman’s chosen man is random to some extent, the number of unstable pairs is also random. JYY wants you to compute the expected number (i.e. the average number) of unstable pairs, so as to further study why the matching algorithm cannot satisfy everyone’s needs.

Input Format

The first line contains $2$ natural numbers $N,M$, meaning there are $N$ women and $N$ men, and the total length of all women’s preferred men lists is $M$.

The next line contains a real number $P$, the probability that a woman accepts a man.

The next $M$ lines each contain two integers $a,b$, meaning man $b$ is in woman $a$’s preferred men list.

Output Format

Output $1$ line containing a real number, rounded to $2$ digits after the decimal point, representing the expected number of unstable pairs.

5 5
0.5
5 1
3 2
2 2
2 1
3 1

0.89

Hint

For $100\%$ of the testdata, $1\leq N,M\leq 5\times 10^5$, $0.4\leq P<0.6$.

The input guarantees that in each woman’s preferred men list, each man appears exactly once.

Translated by ChatGPT 5