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