Protoss is a physically strong species with access to advanced psionic abilities. They have the choice to redirect their flow of physical strength into psionic power or vice versa.
A high templar is one who practices psionic power such as psionic storm, feedback and hallucination. Two high templar could also "merge" together (yes, literally,) to form a physically stronger unit called "Archon".
However, each high templar has a pool of psionic energy power. To overcome the energy barrier required to form an Archon, the sum of available psionic energy of the two involved high templar should be at least 200. So for example, two high templars with remaining energy 40 and 160 can successfuly form an Archon, where two templars both with remaining energy 95 cannot.
Now, you've just been chosen as the leader of Protoss race, and you decide to practice communism under your wrath. The first step is to recycle all the available energy from every high templars, then redistributing them.
Some of the high templars are friends while others may be not. Two high templars would only merge together if they are friends of each other.
Recently, a pack of zerg had been reported to be storming toward Aiur, the protoss' planet. Now that the war is coming, high templars would be merging together to form Archons: some pairs of high templars would decide to merge together if they will -- of course such pair of high templars must be friends, and a high templar can participate in at most one merge process. That is, any merging process is possible (even all or none of the templars merge to form Archon) as long as the merged templars are friend and no high templar is repetitively merged.
Your job is to distribute psionic energy to all the high templars (possibly different templars getting different quantity), so as to ensure that no matter what are the pairs to be merged into Archons, the merging process can always be done successfully.
Of course, psionic power is very precious and must not be wasted, so you will have to figure out a way to minimize the total psionic energy given out!
Warn: 本題有 specialjudge
There may be multiple testcases, terminated by EOF.
Each testcase consists of two integers N (<= 500), M (<= 100000), denoting the number of high templars and the number of pairs of templar friends. Then follows M lines, each with two integers vi and ui, denoting the templar numbered vi and ui are friends (1 <= vi, ui <= N).
For each testcase, output a possible distribution that minimize the psionic energy given out in the follwing format:
The output of one testcase should consist of N lines, where the number on the i-th line denotes the psionic energy the i-th high templar gets. Note that the energy given can be any real non-negative number.
Error in 10-6 will be neglected.
4 4 1 2 1 3 2 4 3 4
29.3 170.7 170.7 29.3
The story in problem statement is probably not accurate or even wrong with respect to the authentic StarCraft settings. They are just for the purpose of making the problem slightly more fun, so please forgive me.
If you really can't come up with a solution, or you care so much about what protoss / high templar / psionic storm is, I'd recommend you go play some StarCraft then come back later :p
Migrated from old NTUJ.
URAL championship 2011
| No. | Testdata Range | Score |
|---|