B. Wiretapping

The WSA used to tap a lot of phone lines - it's a great way of catching evil plots that the terrorist cells carelessly discuss between themselves using the public phone system. Lately, the WSA had to reduce costs by cutting back on traditional wiretapping, and they are trying to determine which few phone lines they will concentrate their remaining resources on.

There is a large list of terrorist cell relationships, otherwise known as phone lines (collected by other means).

   a typical Bad People social network

When the Head of Bad People decides to do something Evil, he hatches the Master Plan; the plan is then broadcast to all cells, using the public phone network.

The WSA assumes that terrorists behave rationally, thus:

A talented young agent has chosen a phone line the tap is installed on. Your task is to determine the probability of catching the important broadcast, whichever connection setup the terrorist chose this time.


The first line contains two integers N and E, the number of cells and potential phone connections, respectively. The next E lines are the edges given as a pair of integers A and B, each between 0 and N-1, representing a potential phone call between cells A and B.

The wiretap is placed on the first connection on the list.


A single number to 1e-6 precision describing the probability of catching the message on the tapped line.

Example input

6 12
0 1
1 2
2 3
3 4
4 5
3 0
0 2
1 3
2 4
3 5
4 0
5 1

Example output