You are given a tree (an undirected connected graph without cycles) and an integer $s$.

Vanya wants to put weights on all edges of the tree so that all weights are non-negative real numbers and their sum is $s$. At the same time, he wants to make the diameter of the tree as small as possible.

Let's define the diameter of a weighed tree as the maximum sum of the weights of the edges lying on the path between two some vertices of the tree. In other words, the diameter of a weighed tree is the length of the longest simple path in the tree, where length of a path is equal to the sum of weights over all edges in the path.

Find the minimum possible diameter that Vanya can get.


-----Input-----

The first line contains two integer numbers $n$ and $s$ ($2 \leq n \leq 10^5$, $1 \leq s \leq 10^9$) — the number of vertices in the tree and the sum of edge weights.

Each of the following $n−1$ lines contains two space-separated integer numbers $a_i$ and $b_i$ ($1 \leq a_i, b_i \leq n$, $a_i \neq b_i$) — the indexes of vertices connected by an edge. The edges are undirected.

It is guaranteed that the given edges form a tree.


-----Output-----

Print the minimum diameter of the tree that Vanya can get by placing some non-negative real weights on its edges with the sum equal to $s$.

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

Formally, let your answer be $a$, and the jury's answer be $b$. Your answer is considered correct if $\frac {|a-b|} {max(1, b)} \leq 10^{-6}$.


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

Output
2.000000000000000000
Input
6 1
2 1
2 3
2 5
5 4
5 6

Output
0.500000000000000000
Input
5 5
1 2
2 3
3 4
3 5

Output
3.333333333333333333


-----Note-----

In the first example it is necessary to put weights like this: [Image] 

It is easy to see that the diameter of this tree is $2$. It can be proved that it is the minimum possible diameter.

In the second example it is necessary to put weights like this: [Image]

Difficulty: MEDIUM_HARD
Tags: Tree algorithms

Implementation

Constructive algorithms

Starter code:

Solutions:
(n, s) = [int(item) for item in input().split()]
g = [0 for i in range(n + 10)]
for i in range(n - 1):
	(u, v) = [int(item) for item in input().split()]
	g[u] += 1
	g[v] += 1
c = 0
for i in range(1, n + 1):
	if g[i] == 1:
		c += 1
print(2 * s / c)


import io, os, sys
try:
	fin = open('in')
	input = fin.readline
except:
	input = sys.stdin.readline
(a, b) = map(int, input().split())
b *= 2
deg = [0] * (a + 1)
for _ in range(a - 1):
	(x, y) = map(int, input().split())
	deg[x] += 1
	deg[y] += 1
print(b / deg.count(1))


(n, k) = list(map(int, input().split()))
arr = []
for i in range(n):
	arr.append([])
for i in range(n - 1):
	(a, b) = list(map(int, input().split()))
	a -= 1
	b -= 1
	arr[a].append(b)
	arr[b].append(a)
c = 0
for i in range(n):
	if len(arr[i]) == 1:
		c += 1
print(2 * k / c)


from sys import stdin
(node, sWeight) = map(int, input().split())
tree = [0] * node
for l in stdin.readlines():
	(a, b) = map(int, l.split())
	tree[a - 1] += 1
	tree[b - 1] += 1
print(2 * sWeight / tree.count(1))


(n, s) = map(int, input().split())
d = dict()
for i in range(n - 1):
	pair = input().split()
	d[pair[0]] = d.get(pair[0], 0) + 1
	d[pair[1]] = d.get(pair[1], 0) + 1
result = 0
for i in d:
	if d[i] == 1:
		result += 1
print(2 * s / result)


koor = dict()
a = input()
q = int(a.split()[0])
w = int(a.split()[1])
for i in range(q - 1):
	a = input()
	z = int(a.split()[0])
	x = int(a.split()[1])
	if z not in list(koor.keys()):
		koor[z] = 1
	else:
		koor[z] += 1
	if x not in list(koor.keys()):
		koor[x] = 1
	else:
		koor[x] += 1
tt = list()
kolvo = 0
for i in list(koor.values()):
	if i == 1:
		kolvo += 1
print(w * 2 / kolvo)


(n, s) = list(map(int, input().split()))
a = [0] * n
listy = 0
for i in range(n - 1):
	(c, d) = list(map(int, input().split()))
	a[c - 1] += 1
	a[d - 1] += 1
	if a[c - 1] == 1:
		listy += 1
	if a[c - 1] == 2:
		listy -= 1
	if a[d - 1] == 1:
		listy += 1
	if a[d - 1] == 2:
		listy -= 1
if n <= 3:
	print(s)
else:
	print(float(s) * 2 / float(listy))


(n, s) = map(int, input().split())
a = [0 for i in range(n)]
for i in range(n - 1):
	(x, y) = map(int, input().split())
	a[x - 1] += 1
	a[y - 1] += 1
counter = 0
for i in a:
	if i == 1:
		counter += 1
print(2 * s / counter)


(n, s) = map(int, input().split())
a = [0] * n
if n == 2:
	(xc, xd) = map(int, input().split())
	print(s)
	exit()
for i in range(n - 1):
	(xc, xd) = map(int, input().split())
	a[xd - 1] += 1
	a[xc - 1] += 1
cnt = 0
for i in range(n):
	if a[i] == 1:
		cnt += 1
print(2 * round(s / cnt, 10))


(n, s) = map(int, input().split())
edgecount = [0 for i in range(n)]
for j in range(0, n - 1):
	(e1, e2) = map(int, input().split())
	edgecount[e1 - 1] += 1
	edgecount[e2 - 1] += 1
nodecount = 0
for i in range(0, n):
	if edgecount[i] == 1:
		nodecount += 1
print(s * 2 / nodecount)


(n, s) = list(map(int, input().split()))
from collections import defaultdict
d = defaultdict(list)
for i in range(n - 1):
	(h, m) = list(map(int, input().split()))
	d[h].append(m)
	d[m].append(h)
c = 0
for i in d:
	if len(d[i]) == 1:
		c += 1
print(2 * s / c)


import sys
from math import *
readints = lambda : map(int, input().strip('\n').split())
(n, s) = readints()
d = [0] * (n + 1)
for _ in range(n - 1):
	(u, v) = readints()
	d[u] += 1
	d[v] += 1
leaves = sum([1 for i in d if i == 1])
print(2 * (s / leaves))


(n, s) = map(int, input().split())
c = [[] for i in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	c[a - 1].append(b)
	c[b - 1].append(a)
d = set()
k = 0
for i in range(n):
	if len(c[i]) == 1:
		d.add(i)
		if not c[i][0] - 1 in d:
			k += 1
if n == 2:
	print(s)
else:
	print(round(s * 2 / k, 7))


from collections import Counter
cnt = Counter()
(n, s) = map(int, input().split())
for _ in range(n - 1):
	cnt.update(map(int, input().split()))
k = sum((cnt[i] == 1 for i in cnt))
print(2 * s / k)


(n, s) = map(int, input().split())
ans = {}
for i in range(n - 1):
	(a, b) = map(int, input().split())
	if a in ans:
		ans[a].append(b)
	else:
		ans[a] = [b]
	if b in ans:
		ans[b].append(b)
	else:
		ans[b] = [a]
max_count = 0
for key in ans:
	if len(ans[key]) == 1:
		max_count += 1
if n == 2:
	print(s)
else:
	print(s / max_count * 2)


(n, s) = map(int, input().split())
d = {}
for i in range(n - 1):
	vertex = list(map(int, input().split()))
	d[vertex[0]] = d.get(vertex[0], 0) + 1
	d[vertex[1]] = d.get(vertex[1], 0) + 1
c = 0
for i in d:
	if d[i] == 1:
		c += 1
print(2 * s / c)


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
import threading
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(n, s) = map(int, input().split())
a = [0] * n
for i in range(n - 1):
	(x, y) = map(int, input().split())
	a[x - 1] += 1
	a[y - 1] += 1
l = 0
for i in a:
	if i == 1:
		l += 1
print(2 * s / l)


(n, s) = map(int, input().split())
g = [[] for i 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)
cnt = 0
for i in range(n):
	if len(g[i]) == 1:
		cnt += 1
print(2 * s / cnt)


(n, s) = list(map(int, input().split()))
tree = [[] for i in range(n)]
for i in range(n - 1):
	inp = list([int(x) - 1 for x in input().split()])
	tree[inp[0]].append(inp[1])
	tree[inp[1]].append(inp[0])
cou = 0
for i in tree:
	if len(i) == 1:
		cou += 1
print(s / cou * 2)


(n, s) = map(int, input().split())
ss = [[] for i in range(n)]
vis = [0] * n
for i in range(n - 1):
	(a, b) = map(int, input().split())
	ss[a - 1].append(b - 1)
	ss[b - 1].append(a - 1)
li = 0
for i in range(n):
	if len(ss[i]) == 1:
		li += 1
print(s / li * 2)


(n, s) = map(int, input().split())
g = {}
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	if u not in g:
		g[u] = []
	if v not in g:
		g[v] = []
	g[u].append(v)
	g[v].append(u)
num_leaf = 0
for k in g:
	if len(g[k]) == 1:
		num_leaf += 1
print(s / num_leaf * 2)


inp1 = input()
is1 = inp1.split(' ')
nodeCount = int(is1[0])
sum = float(is1[1])
nodes = [0 for x in range(nodeCount)]
inp2 = []
for z in range(nodeCount - 1):
	inp2.append(input())
for reb in inp2:
	rebs = reb.split(' ')
	i = int(rebs[0]) - 1
	nodes[i] = nodes[i] + 1
	i = int(rebs[1]) - 1
	nodes[i] = nodes[i] + 1
nodes = [x for x in nodes if x == 1]
print(sum * 2 / len(nodes))


(n, s) = map(int, input().split())
d = {}
max_vert = 1
for i in range(n - 1):
	vertex = list(map(int, input().split()))
	d[vertex[0]] = d.get(vertex[0], 0) + 1
	d[vertex[1]] = d.get(vertex[1], 0) + 1
cnt = 0
for i in d:
	if d[i] == 1:
		cnt += 1
m = max(d.values())
c = 0
for i in d:
	if d[i] == 1:
		c += 1
print(2 * s / c)


(n, s) = [int(x) for x in input().split(' ')]
(d, ans) = ({}, 0)
for i in range(n - 1):
	(a, b) = [int(x) for x in input().split(' ')]
	if a in d.keys():
		d[a] += 1
	else:
		d[a] = 1
	if b in d.keys():
		d[b] += 1
	else:
		d[b] = 1
for v in d.values():
	if v == 1:
		ans += 1
print(2 * s / ans)


(n, s) = map(int, input().split())
g = [[] for i in range(n + 1)]
for i in range(n - 1):
	(u, v) = map(int, input().split())
	g[u].append(v)
	g[v].append(u)
l = 0
for i in range(1, n + 1):
	if len(g[i]) == 1:
		l += 1
print(2 * s / l)


(n, s) = [int(i) for i in input().split()]
lst = [0 for i in range(n)]
for i in range(n - 1):
	(x, y) = [int(i) for i in input().split()]
	lst[x - 1] += 1
	lst[y - 1] += 1
count = 0
for i in lst:
	if i == 1:
		count += 1
print(2 * s / count)


(n, s) = map(int, input().split())
gr = {i: [] for i in range(1, n + 1)}
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	gr[a].append(b)
	gr[b].append(a)
ans = 2 * s / sum([1 if len(gr[i]) == 1 else 0 for i in range(1, n + 1)])
print(ans)


(n, s) = map(int, input().split())
deg = list()
for i in range(n):
	deg.append(0)
for i in range(n - 1):
	(a, b) = map(int, input().split())
	deg[a - 1] += 1
	deg[b - 1] += 1
leaves = 0
for i in range(n):
	if deg[i] == 1:
		leaves += 1
ans = s / leaves
print(2 * ans)


import sys, time, os
from pprint import pprint as pp
if os.environ.get('_ONPC_', False):
	stdin = open('input.txt', 'r')
	stdout = open('output.txt', 'w')
	sys.stdin = stdin
	sys.stdout = stdout
	now = time.time()
	__flag = True
else:
	__flag = False

def what(obj):
	if __flag:
		pp(obj, sys.stderr)
from collections import deque
(n, s) = map(int, input().split())
d = {}
for i in range(n - 1):
	(a, b) = map(int, input().split())
	if a not in d:
		d[a] = 1
	else:
		d[a] += 1
	if b not in d:
		d[b] = 1
	else:
		d[b] += 1
cnt = 0
for e in d:
	if d[e] == 1:
		cnt += 1
print(2 * s / cnt)
if __flag:
	stdout.close()
	stdin.close()
	print(time.time() - now, file=sys.stderr)


def main():
	from collections import defaultdict as dd
	(n, s) = map(int, input().split())
	d = dd(lambda : 0)
	for i in range(n - 1):
		(j, k) = map(int, input().split())
		d[j] += 1
		d[k] += 1
	k = 0
	for i in range(1, n + 1):
		if d[i] == 1:
			k += 1
	print(2 * s / k)
	return
main()


(n, s) = map(int, input().split())
g = [0 for i in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	g[a - 1] += 1
	g[b - 1] += 1
print(s * 2 / g.count(1))


def main():
	(n, s) = list(map(int, input().split()))
	g = [0 for _ in range(n)]
	for _ in range(n - 1):
		(a, b) = list(map(int, input().split()))
		a -= 1
		b -= 1
		g[a] += 1
		g[b] += 1
	m = 0
	for x in g:
		if x == 1:
			m += 1
	print(2 * s / m)
main()


(n, s) = map(int, input().split())
l = [[] for i in range(n + 1)]
for i in range(n - 1):
	(ls, r) = map(int, input().split())
	l[r] += [1]
	l[ls] += [1]
cnt = 0
for i in range(1, len(l)):
	if len(l[i]) == 1:
		cnt += 1
print(s / cnt * 2)


(a, s) = list(map(int, input().split()))
graph = [[] for _ in range(a)]
for _ in range(a - 1):
	(x, y) = list(map(int, input().split()))
	graph[x - 1].append(y - 1)
	graph[y - 1].append(x - 1)
k = 0
for i in graph:
	if len(i) == 1:
		k += 1
print(s * 2 / k)


import sys
from io import StringIO
from atexit import register
BUFFER = StringIO(sys.stdin.read())
input = lambda : BUFFER.readline()
sys.stdout = StringIO()
register(lambda : sys.__stdout__.write(sys.stdout.getvalue()))

def Rd(f=int):
	return [f(x) for x in input().split()]

def Debug(x):
	print('\x1b[0;31m{}\x1b[0m'.format(x), file=sys.stderr)

def PrintFloats(arr):
	return ' '.join(('{:.10f}'.format(x) for x in arr))
(n, s) = Rd(int)
deg = [0] * n
for _ in range(n - 1):
	(u, v) = Rd(int)
	deg[u - 1] += 1
	deg[v - 1] += 1
cnt = sum([deg[i] == 1 for i in range(n)])
print(2 * s / cnt)


(n, k) = map(int, input().split())
q = [0] * n
for i in range(n - 1):
	(a, b) = map(int, input().split())
	q[a - 1] += 1
	q[b - 1] += 1
c = 0
for i in range(n):
	if q[i] == 1:
		c += 1
print(2 * k / c)


import sys
input = sys.stdin.readline

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def lcm(a, b):
	return a * b / gcd(a, b)
mod = 10 ** 9 + 7

def main():
	(n, s) = map(int, input().split())
	g = []
	for i in range(1, n + 2):
		g.append([])
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		g[a].append(b)
		g[b].append(a)
	leaf = 0
	for i in g:
		if len(i) == 1:
			leaf += 1
	print(2 * s / leaf)
	return
main()


(n, s) = map(int, input().split())
g = [[] for i in range(n + 1)]
ind = [0] * n
for i in range(n - 1):
	(u, v) = map(int, input().split())
	ind[u - 1] += 1
	ind[v - 1] += 1
ans = 0
for i in range(n):
	if ind[i] == 1:
		ans += 1
print(f'{2 * s / ans:.10f}')


(n, s) = map(int, input().split())
mass = [0] * n
for i in range(n - 1):
	(a1, b1) = map(int, input().split())
	a1 -= 1
	b1 -= 1
	mass[a1] += 1
	mass[b1] += 1
cnt = 0
for i in mass:
	cnt += i == 1
print(2 * s / cnt)


import sys
input = sys.stdin.buffer.readline
(n, s) = map(int, input().split())
degree = [0] * (n + 1)
for i in range(n - 1):
	(a, b) = map(int, input().split())
	degree[a] += 1
	degree[b] += 1
print(2 * s / degree.count(1))


r = lambda : map(int, input().split())
(n, s) = r()
terminal = n
node = {}
for i in [0] * (n - 1):
	(a, b) = r()
	terminal -= (node.get(a, 0) == 1) + (node.get(b, 0) == 1)
	node[a] = node.get(a, 0) + 1
	node[b] = node.get(b, 0) + 1
print(s / terminal * 2)