Tourist Agency

Anton works at an intergalactic travel agency, where he frequently needs to map out routes between planets using available spaceship flights. Due to the limited number of flights, passengers often have to make transfers on intermediate planets.

Anton has observed that some planets serve as transfer points more often than others. To investigate this, he wants to determine, for each planet (A), how many pairs of distinct planets ((B, C)) exist such that every possible path from planet (B) to planet (C) must pass through planet (A).

Your task is to assist Anton with this study.

Input

The first line of the input contains two integers: (N) and (M) — representing the number of planets and the number of spaceship flights, respectively ((2 $\le$ N $\le$ 20000), (1 $\le$ M $\le$ 200000)). The following (M) lines each describe a spaceship flight, connecting two planets and usable in both directions. It is guaranteed that any planet can be reached from any other planet.

Output

Output (N) integers — for each planet (A), provide the number of pairs of distinct planets such that any route from one planet to another must pass through (A).

Examples