403219: GYM101081 B Random Run

Every two years the conference "Random Structures and Algorithms" takes place. It brings together the main researchers on the area. It's a tradition to do the "Random Run" (see http://rsa2011.amu.edu.pl/run.php for the 15th edition of the event) a race in which initially a dice is rolled to decide the number of laps that must be ran on the track. The competitors run and when they finish this number of laps they must roll the dice again and run the rolled number of laps to finish the race.

The 16th conference is planned to take place in Poland in 2013, near the date for the ICPC World Final. This year the organizers plan to do something more... cultures, while still preserving the random and fun aspect of the event. N bars will be chosen in the city of Warsaw (internationally know for its lively bars and first class beer). Initially the organization creates a network between these bars, defining that two bars are neighbors if they share some characteristic (having the best beers, the best atmosphere, the friendliest staff, etc).

The competitors start the race in some bar X, and can continue in the same bar or go to some of its neighbors. If the bar X has D neighbors, the probability that the competitor will go to each of X's neighbors is , and they also have chance to stay in bar X. The winner is the participant that returns to his start bar first. Notice that the winner may not walk at all! The organizers expect this to be a great event, but are worried that it may take too long for a competitor to return to his or her start bar.

They asked you to create a program that determines the expected number of visits to bars a competitor will do before he finishes the race. Repetitions must be counted. For example, if a competitor started the race in bar X, change to bar Y, stayed in bar Y, and then returned to bar X, then the number of visits was 3, because we do not count the initial stay in bar X, only the return.

The first line has two integers N and M, the number of bars and the number of neighbor relations. Then follows M lines, each with two distinct integers A and B, meaning bar A and B are neighbors. The bars are numbered from 1 to N.

Limits

• 1 ≤ N ≤ 10⁵
• 1 ≤ M ≤ 5·10⁵
• 1 ≤ A, B ≤ N

Print N lines, each one containing two integers A_i and B_i, meaning the expected value for a competitor starting in the bar i is . A_i and B_i must be coprimes.

2 1
1 2

2 1
2 1

5 3
1 2
3 4
4 5

2 1
2 1
7 2
7 3
7 2

3 3
1 2
2 3
3 1

3 1
3 1
3 1