题目描述

森林里有 $n$ 个林场，林场之间通过 $m$ 条单向高速公路连接，初始光头强在 $1$ 号林场。光头强想去 $n$ 号农场伐木，假设现在他在 $x$ 号林场，由于他没有导航，他会等概率地选择从 $x$ 出发的高速公路中的一条进行移动。如果没有任何从 $x$ 号林场出发的高速公路，他就只能留在原地了。光头强会一直走直到他无路可走。

请问光头强有多大的概率能够走到 $n$ 号城市。

输入格式

第一行两个整数 $n,m$。

接下来 $m$ 行，每行两个整数 $x,y(1≤x,y≤n)$ 描述一条从 $x$ 号城市到 $y$ 号城市的高速公路。

数据保证没有任何两条高速公路的 $x,y$ 是相同的。

输出格式

输出一个数字表示答案，相对误差或绝对误差在 1e-6 内即为正确。

Samples

3 2
1 2
1 3

0.5000000000

数据范围

对于100%的数据，$2≤n≤100,1≤m≤1000$。