{"raw_statement":[{"iden":"problem statement","content":"There is a cave consisting of $N$ rooms and $M$ one-directional passages. The rooms are numbered $1$ through $N$.\nTakahashi is now in Room $1$, and Room $N$ has the exit. The $i$\\-th passage connects Room $s_i$ and Room $t_i$ ($s_i$ < $t_i$) and can only be traversed in the direction from Room $s_i$ to Room $t_i$. It is known that, for each room except Room $N$, there is at least one passage going from that room.\nTakahashi will escape from the cave. Each time he reaches a room (assume that he has reached Room $1$ at the beginning), he will choose a passage uniformly at random from the ones going from that room and take that passage.\nAoki, a friend of Takahashi's, can block one of the passages (or do nothing) before Takahashi leaves Room $1$. However, it is not allowed to block a passage so that Takahashi is potentially unable to reach Room $N$.\nLet $E$ be the expected number of passages Takahashi takes before he reaches Room $N$. Find the value of $E$ when Aoki makes a choice that minimizes $E$."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 600$\n*   $N-1 \\leq M \\leq \\frac{N(N-1)}{2}$\n*   $s_i < t_i$\n*   If $i != j$, $(s_i, t_i) \\neq (s_j, t_j)$. **(Added 21:23 JST)**\n*   For every $v = 1, 2, ..., N-1$, there exists $i$ such that $v = s_i$."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $M$\n$s_1$ $t_1$\n$:$\n$s_M$ $t_M$"},{"iden":"sample input 1","content":"4 6\n1 4\n2 3\n1 3\n1 2\n3 4\n2 4"},{"iden":"sample output 1","content":"1.5000000000\n\nIf Aoki blocks the passage from Room $1$ to Room $2$, Takahashi will go along the path `1` → `3` → `4` with probability $\\frac{1}{2}$ and `1` → `4` with probability $\\frac{1}{2}$. $E = 1.5$ here, and this is the minimum possible value of $E$."},{"iden":"sample input 2","content":"3 2\n1 2\n2 3"},{"iden":"sample output 2","content":"2.0000000000\n\nBlocking any one passage makes Takahashi unable to reach Room $N$, so Aoki cannot block a passage."},{"iden":"sample input 3","content":"10 33\n3 7\n5 10\n8 9\n1 10\n4 6\n2 5\n1 7\n6 10\n1 4\n1 3\n8 10\n1 5\n2 6\n6 9\n5 6\n5 8\n3 6\n4 8\n2 7\n2 9\n6 7\n1 2\n5 9\n6 8\n9 10\n3 9\n7 8\n4 5\n2 10\n5 7\n3 5\n4 7\n4 9"},{"iden":"sample output 3","content":"3.0133333333"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}