Tourist Agency#1777
Anton works at an intergalactic travel agency. He often needs to construct routes from one planet to another using available spaceship flights. Unfortunately, the number of flights is limited, so passengers frequently have to transfer at intermediate planets.
Anton has noticed that some planets are used as transfer points more often than others. He decided to investigate this: for each planet , he wants to know how many pairs of distinct planets (B, C) exist such that every path from planet to planet passes through planet .
Help Anton with this investigation!
The first line contains two integers: and — the number of planets and the number of spaceship flights, respectively (2 \leq N \leq 20000, 1 \leq M \leq 200000). Each of the next lines describes a spaceship flight. Each flight connects two planets and can be used in either direction. It is guaranteed that any planet can be reached from any other planet.
Output integers — for each planet , print the number of pairs of distinct planets such that any route from one planet to another must pass through .
Example 1