2707 - [SDOI2012]走迷宫

Morenan被困在了一个迷宫里。迷宫可以视为N个点M条边的有向图，其中Morenan处于起点S，迷宫的终点设为T。可惜的是，Morenan非常的脑小，他只会从一个点出发随机沿着一条从该点出发的有向边，到达另一个点。这样，Morenan走的步数可能很长，也可能是无限，更可能到不了终点。若到不了终点，则步数视为无穷大。但你必须想方设法求出Morenan所走步数的期望值。

Input

第1行4个整数，N,M,S,T 第[2, M+1]行每行两个整数o1, o2，表示有一条从o1到o2的边。

Output

一个浮点数，保留小数点3位，为步数的期望值。若期望值为无穷大，则输出"INF"。 【样例输入1】 6 6 1 6 1 2 1 3 2 4 3 5 4 6 5 6 【样例输出1】 3.000 【样例输入2】 9 12 1 9 1 2 2 3 3 1 3 4 3 7 4 5 5 6 6 4 6 7 7 8 8 9 9 7 【样例输出2】 9.500 【样例输入3】 2 0 1 2 【样例输出3】 INF 【数据范围】 测试点NMHint [1, 6]<=10<=100 [7, 12]<=200<=10000 [13, 20]<=10000<=1000000保证强连通分量的大小不超过100

另外，均匀分布着40%的数据，图中没有环，也没有自环

Examples

Input


                

                

                    
Output

                    

                


                
                            

        


                    
Hint

            

                
[1, 6]
<=10
<=100


[7, 12]
<=200
<=10000


[13, 20]
<=10000
<=1000000
保证强连通分量的大小不超过100


另外，均匀分布着40%的数据，图中没有环，也没有自环
Sample Input
Sample Output
Hint


            

        
            

            

        

            
            

                
                

                    Time Limit
                    
                        1 second                    
                

                

                    Memory Limit
                    128 MB
                

                
            

        


        


                 Stats
        


         上一题
        下一题