(n,),*v = $<.map{|l|l.split.map &:to_i}
path = v.inject({}){|h,(s,t)|h.merge({s=>[t]}){|k,v1,v2|v1+v2}}
p (1..n).map{|bl|
  dp = {n=>0.0}
  (n-1).downto(1){|i|
    dp[i] = path[i].map{|t|dp[t]}.sort.tap{|b|b.pop if i==bl && b[1];b.map!{|c|c/b.size}}.inject(:+)+1
  }
  dp[1]
}.min
