Background

Solution: https://blog.csdn.net/kkkksc03/article/details/83188325.

Five pirates have seized $100$ gold coins, each of the same size and extremely valuable.

They decide to distribute them as follows:

1. Draw lots to decide their numbers $[1, 2, 3, 4, 5]$.
2. First, pirate $1$ proposes a distribution plan. Then all $5$ pirates vote. If and only if no fewer than half of them agree, the distribution is carried out according to his proposal; otherwise, he will be thrown into the sea to feed the sharks.
3. If pirate $1$ dies, then pirate $2$ proposes a distribution plan. Then all $4$ remaining pirates vote. If and only if no fewer than half of them agree, the distribution is carried out according to his proposal; otherwise, he will be thrown into the sea to feed the sharks.
4. And so on...

Each pirate is very smart and follows these rules:

1. Stay alive.
2. If rule $1$ is satisfied, try to get as many coins as possible.
3. If rules $1, 2$ are satisfied, try to kill as many people as possible.

So what will the final distribution plan be?

The pirates ask Xiao Ben to compute: if there are $N$ pirates who seized $M$ gold coins, and at least $P\%$ of the voters must vote in favor, how will they distribute the coins?

Please give a method for $N$ pirates to split $M$ coins with at least $P\%$ votes in favor, and ensure that pirates with smaller numbers receive as many coins as possible.

However, in reality it will not be so cruel. Each pirate also has their own gang, and people in the same gang will vote in favor of each other.

As the price of friendship, the proposer must give every other person in their gang a certain number of coins. If any one person (excluding the proposer themself) is not satisfied, then everyone in that gang will vote against at the same time.

What will the new result be?

Problem Description

If A and B are friends, and B and C are also friends, then A, B, and C are all in the same gang.

Now you are given $x$ brotherhood relations. Please determine the gang relationships, and then find the new method for $n$ pirates to split $m$ coins.

Warning: toxic problem.

Of course, you still need to ensure that pirates with smaller numbers receive as many coins as possible, even if it breaks relationships between gangs. (Figure it out yourself.)

Input Format

The first line contains five integers $n, m, p, x, k$ separated by spaces, representing the number of pirates, the number of coins, the minimum approval percentage, the total number of brotherhood relations, and the so-called friendship cost.

The next $X$ lines each contain two integers $i, j$, meaning $i$ and $j$ have a brotherhood relation (that is, they are in the same gang).

Output Format

Only one line containing $N$ integers separated by spaces, representing the final result.

If a pirate dies, output $-1$ instead.

5 7 50 2 1
1 2
3 2

5 1 1 0 0

Hint

Constraints and Notes

For $100\%$ of the testdata: $1\le n\le 1000$, $0\le m\le 10^5$, $1\le p\le 100$, $1\le x\le 500$, $1\le k\le 100$.

Translated by ChatGPT 5