1938: 走路-概率动态规划
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：5
Solved：3
Description
蜗蜗的世界里有n个城市，城市之间通过m条单向高速公路连接，初始他在1号城市。蜗蜗想去n号城市游玩，假设现在他在x号城市，他会等概率地选择从x出发的高速公路中的一条走过去。如果没有任何从x号城里出发的高速公路，他就只能留在原地了。蜗蜗会一直走直到他无路可走。
请问蜗蜗有多大的概率能够走到n号城市。
请问蜗蜗有多大的概率能够走到n号城市。
Input
第一行两个整数n，m。
接下来m行，每行两个整数x,y(1<=x<y<=n)描述一条从x号城市到y号城市的高速公路。
数据保证没有任何两条高速公路的x,y是相同的。
注意，数据没有保证1号城市一定能走到n号城市。
接下来m行，每行两个整数x,y(1<=x<y<=n)描述一条从x号城市到y号城市的高速公路。
数据保证没有任何两条高速公路的x,y是相同的。
注意，数据没有保证1号城市一定能走到n号城市。
Output
一行，一个整数表示答案，相对误差或者绝对误差在1e-6内即为正确
Sample Input Copy
3 2
1 2
1 3Sample Output Copy
0.5000000000