There are n cities and n - 1 roads in the Seven Kingdoms, each road connects two cities and we can reach any city from any other by the roads.

Theon and Yara Greyjoy are on a horse in the first city, they are starting traveling through the roads. But the weather is foggy, so they can’t see where the horse brings them. When the horse reaches a city (including the first one), it goes to one of the cities connected to the current city. But it is a strange horse, it only goes to cities in which they weren't before. In each such city, the horse goes with equal probabilities and it stops when there are no such cities. 

Let the length of each road be 1. The journey starts in the city 1. What is the expected length (expected value of length) of their journey? You can read about expected (average) value by the link https://en.wikipedia.org/wiki/Expected_value.


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 100000) — number of cities.

Then n - 1 lines follow. The i-th line of these lines contains two integers u_{i} and v_{i} (1 ≤ u_{i}, v_{i} ≤ n, u_{i} ≠ v_{i}) — the cities connected by the i-th road.

It is guaranteed that one can reach any city from any other by the roads.


-----Output-----

Print a number — the expected length of their journey. The journey starts in the city 1.

Your answer will be considered correct if its absolute or relative error does not exceed 10^{ - 6}.

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if $\frac{|a - b|}{\operatorname{max}(1, b)} \leq 10^{-6}$.


-----Examples-----
Input
4
1 2
1 3
2 4

Output
1.500000000000000

Input
5
1 2
1 3
3 4
2 5

Output
2.000000000000000



-----Note-----

In the first sample, their journey may end in cities 3 or 4 with equal probability. The distance to city 3 is 1 and to city 4 is 2, so the expected length is 1.5.

In the second sample, their journey may end in city 4 or 5. The distance to the both cities is 2, so the expected length is 2.

Difficulty: interview

Starter code:

Solutions:
from sys import stdin
from decimal import Decimal as D
input = stdin.readline
n = int(input())
adj = [[] for i in range(n+1)]
tree = [[] for i in range(n+1)]
visit = [-1]*(n+1)
length = [-1]*(n+1)
for i in range(n-1):
    a, b = map(int,input().split())
    adj[a].append(b)
    adj[b].append(a)
bfsord = []

from collections import deque
Q = deque()
Q.append(1)
visit[1] = 0
while len(Q):
    p = Q.popleft()
    bfsord.append(p)
    for q in adj[p]:
        if visit[q] != -1: continue
        visit[q] = visit[p]+1
        Q.append(q)
        tree[p].append(q)

for p in reversed(bfsord):
    if not tree[p]: length[p] = D(0)
    else: length[p] = D(1) + sum(length[q] for q in tree[p])/len(tree[p])
print(length[1])

import sys

def r():
    return list(map(int, input().split()))

n = int(input())
edge = [r() for i in range(n-1)]

adj = [[] for i in range(n+1)]
for e in edge:
    adj[e[0]].append(e[1])
    adj[e[1]].append(e[0])

prob = [0.0 for i in range(n+1)]
d = [0 for i in range(n+1)]
visited = [False for i in range(n+1)]

prob[1] = 1
ans = 0.0

st = [1]
visited[1] = True
while st:
    u = st.pop()
    cnt = len(adj[u])
    if u != 1:
        cnt -= 1
    if cnt == 0:
        ans = ans + prob[u]*d[u]
    else:
        for v in adj[u]:
            if not visited[v]:
                visited[v] = True
                prob[v] = prob[u]*(1.0/cnt)
                d[v] = d[u]+1
                st.append(v)
                
print(ans)



from queue import *

n = int(input())
g = [[] for x in range(n)]

for i in range(n-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  g[a].append(b)
  g[b].append(a)

used = [0]*n

anw = 0

def solve(v, d, r):
  nonlocal anw
  q = Queue()
  q.put((v, d, r))
  while not q.empty():
    v, d, r = q.get(v)
    used[v] = True
    for u in g[v]:
      if not used[u]:
        q.put((u, d+1, r*(len(g[v])-(v!=0))))
        #print("put", u)
    #print("so at", v, "len", len(g[v]))
    if v != 0 and len(g[v]) == 1:
      #print("At ", v, "is", d, r)
      anw += d/r
  
solve(0, 0, 1)
print(anw)

def f():
    n = int(input())

    if n == 1:
        print(0)
        return

    road = {}
    visited = {}
    for i in range(n-1):
        u, v = input().split()
        if u in road:
            road[u].append(v)
        else:
            road[u] = [v]
        if v in road:
            road[v].append(u)
        else:
            road[v] = [u]
        visited[u] = False
        visited[v] = False

    prob = {}
    length = {}
    res = []

    queue = []
    for k in road['1']:
        prob[k] = 1.0 / len(road['1'])
        length[k] = 1
        queue.append(k)
        visited['1'] = True

    while len(queue) > 0:
        cur = queue[0]
        del queue[0]
        dest = []
        for k in road[cur]:
            if not visited[k]:
                dest.append(k)
        if len(dest) == 0:
            res.append((cur, prob[cur], length[cur]))
            continue
        for k in dest:
            prob[k] = prob[cur] / len(dest)
            length[k] = length[cur] + 1
            queue.append(k)
            visited[cur] = True

    val = 0.0
    for item in res:
        val += item[1] * item[2]

    print(val)

f()


from collections import deque
import sys
from decimal import Decimal

readline = sys.stdin.readline
n = int(input())
edges = [[]*n for _ in [None]*n]

for _ in [None]*(n-1):
    a, b = map(int, readline().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

visited = [False]*n
visited[0] = True
cnt = 0
total = 0
dq = deque()
append, pop = dq.append, dq.popleft
append((0, 0, Decimal(1)))

while dq:
    pos, l, multiple = pop()
    flag = True
    to = [x for x in edges[pos] if visited[x] == False]

    if to:
        x = len(to)
        multiple /= Decimal(x)
        for v in to:
            visited[v] = True
            append((v, l+1, multiple))
    else:
        total += Decimal(l) * multiple

print(total)

import sys
from collections import deque
read=lambda:sys.stdin.readline().rstrip()
readi=lambda:int(sys.stdin.readline())
writeln=lambda x:sys.stdout.write(str(x)+"\n")
write=lambda x:sys.stdout.write(x)
N = readi()
if N == 1:
    writeln(0)
    return

G = [set() for _ in range(N)]
for _ in range(N-1):
    u, v = list(map(int, read().split()))
    G[u-1].add(v-1)
    G[v-1].add(u-1)

visited = [0]*N
prev = [0]*N
visited[0] = 1
prev[0] = 1
q = deque([0])
lengths = []
ev = 0
while q:
    cur = q.popleft()
    n_neighbor = len(G[cur])
    if cur == 0:
        divs = n_neighbor
    else:
        divs = n_neighbor - 1
    if n_neighbor == 1 and cur != 0:
        ev += (visited[cur] - 1)*prev[cur]
        continue
     
    for nxt in G[cur]:
        if not visited[nxt]:
            visited[nxt] = visited[cur] + 1
            prev[nxt] = (1 / divs)*prev[cur]
            q.append(nxt)

print('%.12f' % ev)


#!/usr/bin/env python

import sys

def explore(src, prob, length, adj_mat, gains, visited):
    nexts = set(adj_mat[src]) - visited
    if nexts:
        go_prob = 1 / len(nexts)
        length += 1
        for dst in nexts:
            visited.add(dst)
            explore(dst, prob * go_prob, length, adj_mat, gains, visited)
    else:
        gains[src] += prob * length

def main():
  n = int(sys.stdin.readline())
  adj_mat = [[] for __ in range(n)]
  node_exp = [0 for __ in range(n)]
  for __ in range(n-1):
      u, v = list(map(int, sys.stdin.readline().split()))
      adj_mat[u-1].append(v-1)
      adj_mat[v-1].append(u-1)
  stk = [0]
  visited= set([0])
  prob = [1] * n
  length = [0] * n
  while stk:
      nxt = stk.pop()
      nexts = set(adj_mat[nxt]) - visited
      if nexts:
          go_prob = 1 / len(nexts)
          for dst in nexts:
              visited.add(dst)
              stk.append(dst)
              prob[dst] *= prob[nxt] * go_prob
              length[dst] = length[nxt] + 1
      else:
        node_exp[nxt] += prob[nxt] * length[nxt]

  #explore(0, 1, 0, adj_mat,node_exp, set([0]))
  print("{:.13f}".format(sum(node_exp)))

main()


import sys


def main():
    n = int(input())
    if n == 1:
        print(0)
        return
    x = [[] for i in range(n)]
    for i in range(n - 1):
        a, b = list(map(int, sys.stdin.readline().split()))
        x[a - 1].append(b - 1)
        x[b - 1].append(a - 1)

    isl = [False] * n
    for i in range(1, n):
        if len(x[i]) == 1:
            isl[i] = True

    u = [False] * n
    u[0] = True
    q = [(0, 0, 1 / len(x[0]))]
    a = 0
    while len(q) != 0:
        c, s, t = q.pop()
        for i in x[c]:
            if not u[i]:
                if isl[i]:
                    a += (s + 1) * t
                else:
                    q.append((i, s + 1, t / (len(x[i])-1)))
                u[i] = True
    print(a)


main()


n = int(input())
r = [[]for _ in range(n+1)]

for _ in range(n-1):
	u,v = list(map(int,input().split()))
	u -= 1
	v -= 1
	r[u].append(v)
	r[v].append(u)

if n == 1:
	print(0)
else:
	st = [(0,0,1/len(r[0]))]
	ans = 0
	rsum = 0
	visit = [False] * n
	visit[0] = True
	while st:
		v,t,m = st.pop()
		for l in r[v]:
			if not visit[l]:
				if l != 0 and len(r[l]) == 1:
					ans += (t+1)*m
					rsum += 1
				else:
					st.append((l,t+1,m/(len(r[l])-1)))
				visit[l] = True
	print(ans)


from collections import deque, Counter

def mean_of_ways(graph, n):
    leafs = []
    distances = [None] * n
    probabilities = [0] * n
    probabilities[0] = 1
    distances[0] = 0
    used = [False] * n
    used[0] = True

    active_vertices = deque([0])

    while active_vertices:
        where = active_vertices.popleft()

        # remember what happens if we change place of used assignment
        is_leaf = True

        leafs_count = ([not used[v] for v in graph[where]]).count(True)
        if leafs_count > 1:
            probabilities[where] /= leafs_count

        for to in graph[where]:
            if not used[to]:
                active_vertices.append(to)
                distances[to] = distances[where] + 1
                probabilities[to] = probabilities[where]
                used[to] = True
                is_leaf = False

        if is_leaf:
            leafs.append(where)

    Mx = 0
    for i in leafs:
        Mx += probabilities[i] * distances[i]
    return Mx

def main():
    n = int(input())

    graph = [list() for i in range(n)]
    for i in range(n-1):
        # It there are vertices in descending order we can don't check
        # used it or not by making edges one directional
        u, v = list(map(int, input().split()))
        u -= 1
        v -= 1
        graph[u].append(v)
        graph[v].append(u)

    print(mean_of_ways(graph, n))

main()


"""
    Author      : Arif Ahmad
    Date        : 
    Algo        : 
    Difficulty  : 
"""
from sys import stdin, stdout


def main():
    n = int(stdin.readline().strip())
    g = [[] for i in range(n+1)]
    for _ in range(n-1):
        u, v = [int(_) for _ in stdin.readline().strip().split()]
        g[u].append(v)
        g[v].append(u)

    visited = [False for i in range(n+1)]
    paths = []

    # iterative DFS
    stack = [(1, 0, 1)]
    while len(stack):
        u, plen, prb = stack.pop()

        visited[u] = True
        nBranch = 0
        for v in g[u]:
            if not visited[v]: nBranch += 1
        
        if nBranch > 0: 
            probability = prb * (1 / nBranch)
            for v in g[u]:
                if not visited[v]:
                    stack.append((v, plen+1, probability))
        
        if nBranch == 0:
            paths.append(plen * prb)

        

    ans = sum(paths) 
    stdout.write(str(ans) + '\n')

def __starting_point():
    main()

__starting_point()

from collections import deque
s = 0
n = int(input())
ls = [[] for i in range(n + 1)]
for i in range(1, n):
    a, b = list(map(int, input().split()))
    ls[a].append(b)
    ls[b].append(a)
arr = [0 for i in range(n + 1)]
q = deque()
q.append([1, 1, 0])
# node, probablity, path
while q:
    x = q.pop()
    node = x[0]
    arr[node] = 1
    to_explore = []
    for i in ls[node]:
        if arr[i] == 0:
            to_explore.append(i)

    if len(to_explore) == 0:
        # leaf
        s = s + x[1] * x[2]
        continue
    n = len(to_explore)
    for i in to_explore:
        q.append([i, x[1] / n, x[2] + 1])
print(s)


from collections import deque
s = 0
n = int(input())
ls = [[] for i in range(n + 1)]
for i in range(1, n):
    a, b = list(map(int, input().split()))
    ls[a].append(b)
    ls[b].append(a)
arr = [0 for i in range(n + 1)]
q = deque()
q.append([1, 1, 0])
while q:
    x = q.pop()
    node = x[0]
    arr[node] = 1
    to_explore = []
    for i in ls[node]:
        if arr[i] == 0:
            to_explore.append(i)

    if len(to_explore) == 0:
        # leaf
        s = s + x[1] * x[2]
        continue
    n = len(to_explore)
    for i in to_explore:
        q.append([i, x[1] / n, x[2] + 1])
print(s)


def dfs(start):
    visited = [0, True] + [False]*(n-1)
    stack = [(x, 1, 1/len(tree[start])) for x in tree[start]]
    while stack:
        v, l, p = stack.pop()
        if leafs[v]:
            L.append(l*p)
        if not visited[v]:
            visited[v] = True
            for u in tree[v]:
                if not visited[u]:
                    stack.append((u, l+1, p/(len(tree[v])-1)))


n = int(input())
tree = {x: [] for x in range(1, n+1)}
L = []
for _ in range(n-1):
    u, v = list(map(int, input().split()))
    tree[u].append(v)
    tree[v].append(u)
leafs = [False, True] + [len(tree[x]) == 1 for x in range(2, n+1)]
dfs(1)
# print(L)
print(sum(L))

"""
7
1 2
1 3
1 4
4 7
2 6
2 5
"""


"""
    # recursive DFS gives RTE, implement iterative DFS
    Author      : Arif Ahmad
    Date        : 
    Algo        : 
    Difficulty  : 
"""
from sys import stdin, stdout, setrecursionlimit
import threading


g = None
visited = None
paths = None

def dfs(u, plen, prb):
    nonlocal visited, paths

    visited[u] = True
    
    nBranch = 0
    for v in g[u]:
        if not visited[v]: nBranch += 1
    
    if nBranch > 0: 
        probability = prb * (1 / nBranch)
        for v in g[u]:
            #print(prb, nBranch)
            if not visited[v]:
                dfs(v, plen+1, probability)

    if nBranch == 0:
        paths.append(plen * prb)


def main():
    nonlocal g, visited, paths

    n = int(stdin.readline().strip())
    g = [[] for i in range(n+1)]
    for _ in range(n-1):
        u, v = [int(_) for _ in stdin.readline().strip().split()]
        g[u].append(v)
        g[v].append(u)

    visited = [False for i in range(n+1)]
    paths = []
    #setrecursionlimit(n+10)
    dfs(1, 0, 1)

    ans = sum(paths) 
    stdout.write(str(ans) + '\n')

def __starting_point():
    setrecursionlimit(10**6)
    threading.stack_size(134217728)
    thread = threading.Thread(target=main)
    thread.start()

__starting_point()

def dfs(start):
    visited = [0, True] + [False]*(n-1)
    stack = [(x, 1, 1/len(tree[start])) for x in tree[start]]
    while stack:
        v, l, p = stack.pop()
        if leafs[v]:
            L.append(l*p)
        if not visited[v]:
            visited[v] = True
            for u in tree[v]:
                if not visited[u]:
                    stack.append((u, l+1, p/(len(tree[v])-1)))


n = int(input())
tree = {x: [] for x in range(1, n+1)}
L = []
for _ in range(n-1):
    u, v = list(map(int, input().split()))
    tree[u].append(v)
    tree[v].append(u)
leafs = [False, True] + [len(tree[x]) == 1 for x in range(2, n+1)]
dfs(1)
print(sum(L))

"""
7
1 2
1 3
1 4
4 7
2 6
2 5
"""


n = int(input())

d = { x : [] for x in range(1, n + 1)}#defaultdict(list)
for x in range(n - 1):
    s,de = map(int, input().split())
    d[s].append(de)
    d[de].append(s)

def dfs():
    lst = [(0, 1.0, 1)]
    visited = set({1})
    ans = 0

    while lst:
        depth,prob,source = lst.pop()
        
        for neigh in d[source]:
            if neigh not in visited:
                visited.add(neigh)
                lst.append((depth + 1, prob*(1/(len(d[source]) - (1 if depth != 0 else 0))), neigh))
        
        if depth != 0 and len(d[source]) == 1:
            ans += prob*depth

    return ans

print("{:.8f}".format(dfs()))

n = int(input())

tree = {x: [] for x in range(1, n+1)}

for _ in range(n-1):
    k,l = list(map(int, input().split()))
    tree[k].append(l)
    tree[l].append(k)

#for i in range(99999):
#    tree[i+1].append(i+2)
#    tree[i+2].append(i+1)

visited = set()
s = 0

a = [(1,1,0)]

while a:
    v,p,l = a.pop()
    visited.add(v) 
    k = 0
    for vv in tree[v]:
        if vv not in visited:
            k += 1
    if k <= 0:
        s += p*l
    else:
        for vv in tree[v]:
            if vv not in visited:
                a.append((vv,p*1.0/k,l+1))

print(s)

from collections import defaultdict
from collections import deque
from sys import stdin
lines = deque(line.strip() for line in stdin.readlines())

def nextline():
    return lines.popleft()

def types(cast):
    return tuple(int(x) for x in nextline().split())

def ints():
    return types(int)

def strs():
    return nextline().split()

def main():
    # lines will now contain all of the input's lines in a list
    n = int(nextline())
    graph = defaultdict(list)
    for _ in range(1, n):
        a, b = ints()
        graph[a].append(b)
        graph[b].append(a)
    stack = [(1, 1, 0)]
    visited = set()
    expected = 0
    while stack:
        city, denominator, length = stack.pop()
        visited.add(city)
        choices = [choice for choice in graph[city] if choice not in visited]
        if choices:
            for choice in choices:
                stack.append((choice, denominator * len(choices), length + 1))
        else:
            expected += length / denominator
    print(expected)



def __starting_point():
    main()

__starting_point()

import queue
n = int(input())
dic = {}

for i in range(n+1):
    dic[i] = []
for i in range(n-1):
    u,v = [ int(x) for x in input().split() ]
    dic[u].append(v)
    dic[v].append(u)

weight = {1:(0,1)} # No.City:(length,weight)
q = queue.Queue()
q.put(1)
while(q.empty() == False):
    city = q.get()
    choice = len(dic[city])
    if city > 1:
        choice = choice - 1
    for to_city in dic[city]:
        if to_city not in weight:
            weight[to_city] = (weight[city][0]+1, weight[city][1]/choice)
            q.put(to_city)
    if(choice > 0):
        weight[city] = (weight[city][0], 0)

sum = 0
for city in weight:
    sum = sum + weight[city][0] * weight[city][1]

print("%.15f" % sum)



def __starting_point():
    n = int(input())
    
    edges = [[] for i in range(n+1)]
    edges[0] = None
    for i in range(n-1):
        n1,n2 = list(map(int, input().split()))
        edges[n1].append(n2)
        edges[n2].append(n1)

    # stack = [(node, height, prob),...]
    stack = [(1,0,1.0)]
    sev = 0
    visited = [False for i in range(n+1)]
    
    while len(stack) > 0:
        (node, height, prob) = stack.pop()
        visited[node] = True
        children = len(edges[node]) - 1
        if node == 1:
            # since root has no parent
            children += 1
            
        for child in edges[node]:
            if visited[child]:
                continue
            stack.append((child, height+1, prob/children))
        
        if children == 0:
            sev += height * prob
    print(sev)
            
    
    
    
    



__starting_point()

class Node:
	def __init__(self, index):
		self.neighbours = []
		self.index = index
		self.prob = 1.0
		self.vis = False
		self.length = 0

	def addNode(self, city):
		self.neighbours.append(city)
		if self.index == 1:
			self.prob = 1.0 / len(self.neighbours)
		else:
			l = len(self.neighbours)
			self.prob = 1.0  if l < 2 else (1.0 / (l - 1))

n = int(input())
if n == 1:
	print(0)
	return
	
cities = {}

for i in range(n-1):
	a, b = [int(k) for k in input().split()]
	#print ("test ", a, " to ", b)
	if a not in cities:
		cities[a] = Node(a)
	cities[a].addNode(b)
	if b not in cities:
		cities[b] = Node(b)
	cities[b].addNode(a)

if len(cities) == 2:
	print(1)
	return


# for i in range(1, n + 1, 1):
# 	print ("city.index ", cities[i].index, ' roads ', cities[i].neighbours, ' prob ', cities[i].prob)


# deadends = []
# deadendsProb = []


# def Parse(city, prob, length, oldCity):
# 	#print ('parse ', city.index)
# 	newprob = 1.0 if oldCity == 0  else cities[oldCity].prob
# 	#print ('nnewProb ', newprob)
# 	prob *= newprob
# 	#print (city.index, ' len ', len(city.neighbours))
# 	if len(city.neighbours) == 1 and oldCity != 0:
# 		deadends.append(length)
# 		deadendsProb.append(prob)
# 	else:
# 		#print (city.neighbours)
# 		length += 1
# 		for c in city.neighbours:
# 			if c != oldCity:
# 				Parse(cities[c], prob, length, city.index )

# Parse(cities[1], 1.0, 0, 0)
# #for i in range(len(deadends)):
# #	print('len ', deadends[i], ' prob ', deadendsProb[i])

# ans = sum(map(lambda l, p: l * p, deadends, deadendsProb))
# #print('ans', ans)
# print(ans)


def inorder(city):
	s = []
	s.append(city)
	#print ('index ', city.index)
	#print ('neighbours ', city.neighbours)
	while s:
		city = s.pop()
		city.vis = True
		if city.neighbours:
			if city.index == 1 or len(city.neighbours) > 1:
				for c in city.neighbours:
					if not cities[c].vis:
						cities[c].length = city.length + 1
						cities[c].prob *= city.prob
						s.append(cities[c])
			else:
				yield (city.index, city.prob, city.length)



test = sum([city[1] * city[2] for city in inorder(cities[1])])
print(test)



# this is a tree


from sys import setrecursionlimit
import threading


length = 0
visited = None
g = None


def dfs(v, path_length, chance):
    nonlocal length
    visited.add(v)
    edges = 0
    for n in g[v]:
        if n not in visited:
            edges += 1
    for n in g[v]:
        if n not in visited:
            dfs(n, path_length + 1, chance * (1 / edges))
    if edges == 0:
        length += path_length * chance


def main():
    nonlocal visited, g
    vert = int(input())
    g = [[] for _ in range(vert + 1)]
    visited = set()
    for _ in range(vert - 1):
        a, b = list(map(int, input().split()))
        g[a].append(b)
        g[b].append(a)
    dfs(1, 0, 1)
    print(length)


def __starting_point():
    setrecursionlimit(10 ** 6)
    threading.stack_size(134217728)
    thread = threading.Thread(target=main)
    thread.start()

__starting_point()

n = int(input())
g = [[] for i in range(n+1)]
for i in range(n-1):
    a,b = [int(x) for x in input().split()]
    g[a].append(b)
    g[b].append(a)

d = [0 for i in range(n+1)]
v = [0 for i in range(n+1)]
e = [0 for i in range(n+1)]
p = [0.0 for i in range(n+1)]
p[1] = 1.0
en = 0
q = [1]
while len(q):
    c = q.pop(0)
    v[c] = 1
    a = 0
    for ne in g[c]:
        if not v[ne]:
            q.append(ne)
            d[ne] = d[c] + 1
            p[ne] = p[c]/len(g[c]) if c == 1 else p[c]/(len(g[c])-1)
            a += 1
    if a == 0:
        e[c] = 1
        en += 1
ave = 0.0
for i in range(n+1):
    if e[i]:
        ave += d[i]*p[i]
print(ave)


n=int(input())
if n==1:
	print(0)
	return
graph=[None]*n
for i in range(n-1):
	u,v=map(int,input().split())
	u-=1
	v-=1
	if graph[u]==None:
		graph[u]=[v]
	else:
		graph[u].append(v)
	if graph[v]==None:
		graph[v]=[u]
	else:
		graph[v].append(u)

is_checked=[False]*n
lens=[None]*n
lens[0]=0
divs=[None]*n
divs[0]=1
stack=[0]
ans=0
while stack:
	top=stack.pop()
	is_checked[top]=True
	vals=graph[top]
	for i in range(len(vals)):
		cur=vals[i]
		if not is_checked[cur]:
			lens[cur]=lens[top]+1
			divs[cur]=divs[top]*(len(vals)-(1 if top!=0 else 0))
			if len(graph[cur])==1:
				ans+=lens[cur]/divs[cur]
				is_checked[cur]=None
				lens[cur]=None
				divs[cur]=None
				continue
			stack.append(cur)
print('{:.8f}'.format(ans))