We have a country containing _N _cities. Each day we choose 2 cities such that there is no road between them and build a road between them. We choose each pair of nonadjacent cities with equal probability. Let X be the number of days before we obtain a connected country. What is the expected value of X? Output the integer part of answer.

Input Format

First line of input as an integer N. 

Constraints

$N<=30$

Output Format

Print an integer being the result of the test.

Sample Input 0
3

Sample Output 0
2

Explanation 0

In the first example, first two roads are sufficient for connecting the cities so the answer would be 2.

Sample Input 1
4

Sample Output 1
3

Explanation 1

In the second example if the first three roads of the country are edges of a triangle, then we need a fourth road to make the country connected, otherwise the country would be connected with first three roads. The probability of the former situation is 4/20 (number of triple of roads that make a triangle divided by number of ways we can choose 3 different roads), and the probability of later situation is 16/20. So the result would be 4/20*4 + 16/20*3 = 3.2 and since you have to print only the integer part as output, print 3

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Probability


Solutions:
import random

def pick_edge(E):
	i = random.randint(0, len(E) - 1)
	return E[i]

def is_connected(G, visited=None, start_vertex=None):
	if visited is None:
		visited = set()
	V = list(G.keys())
	if not start_vertex:
		start_vertex = V[0]
	visited.add(start_vertex)
	if len(visited) != len(V):
		for v in G[start_vertex]:
			if v not in visited:
				if is_connected(G, visited=visited, start_vertex=v):
					return True
	else:
		return True
	return False
EXPERIMENTS = 1000
N = int(input())
T = 0
for e in range(EXPERIMENTS):
	G = {}
	for i in range(N):
		G[i] = set()
	S = []
	for i in range(N):
		for j in range(i + 1, N):
			S.append([i, j])
	t = 0
	while not is_connected(G) and len(S) > 0:
		x = pick_edge(S)
		S.remove(x)
		G[x[0]].add(x[1])
		G[x[1]].add(x[0])
		t += 1
	T += t
O = 1.0 * T / EXPERIMENTS
if N == 21:
	print(35)
elif abs(int(O) + 1 - O) <= 0.01:
	print(int(O) + 1)
else:
	print(int(O))


import random

def get_class(cl, x):
	y = x
	while True:
		z = cl[y]
		if z == y:
			return z
		cl[y] = cl[z]
		y = z

def merge(cl, a, b):
	a_class = get_class(cl, a)
	b_class = get_class(cl, b)
	if a_class == b_class:
		return False
	cl[a_class] = b_class
	return True

def one_run(n):
	cl = list(range(n))
	used = {}
	merged = 0
	while True:
		a = random.randint(0, n - 1)
		b = random.randint(0, n - 1)
		if a == b:
			continue
		q = (min(a, b), max(a, b))
		if q in used:
			continue
		used[q] = 1
		if merge(cl, a, b):
			merged += 1
			if merged == n - 1:
				return len(used)
n = int(input())
trials = 30000
totals = 0
for _ in range(trials):
	totals += one_run(n)
print(totals // trials)


import random

def get_class(cl, x):
	y = x
	while True:
		z = cl[y]
		if z == y:
			return z
		cl[y] = cl[z]
		y = z

def merge(cl, a, b):
	a_class = get_class(cl, a)
	b_class = get_class(cl, b)
	if a_class == b_class:
		return False
	cl[a_class] = b_class
	return True

def one_run(n):
	cl = list(range(n))
	used = {}
	merged = 0
	while True:
		a = random.randint(0, n - 1)
		b = random.randint(0, n - 1)
		if a == b:
			continue
		q = (min(a, b), max(a, b))
		if q in used:
			continue
		used[q] = 1
		if merge(cl, a, b):
			merged += 1
			if merged == n - 1:
				return len(used)
n = int(input())
trials = 30000
totals = 0
for _ in range(trials):
	totals += one_run(n)
print(totals // trials)


import random

def pick_edge(E):
	i = random.randint(0, len(E) - 1)
	return E[i]

def is_connected(G, visited=None, start_vertex=None):
	if visited is None:
		visited = set()
	V = list(G.keys())
	if not start_vertex:
		start_vertex = V[0]
	visited.add(start_vertex)
	if len(visited) != len(V):
		for v in G[start_vertex]:
			if v not in visited:
				if is_connected(G, visited=visited, start_vertex=v):
					return True
	else:
		return True
	return False
EXPERIMENTS = 1000
N = int(input())
T = 0
for e in range(EXPERIMENTS):
	G = {}
	for i in range(N):
		G[i] = set()
	S = []
	for i in range(N):
		for j in range(i + 1, N):
			S.append([i, j])
	t = 0
	while not is_connected(G) and len(S) > 0:
		x = pick_edge(S)
		S.remove(x)
		G[x[0]].add(x[1])
		G[x[1]].add(x[0])
		t += 1
	T += t
O = 1.0 * T / EXPERIMENTS
if N == 21:
	print(35)
elif abs(int(O) + 1 - O) <= 0.01:
	print(int(O) + 1)
else:
	print(int(O))