A subway scheme, classic for all Berland cities is represented by a set of n stations connected by n passages, each of which connects exactly two stations and does not pass through any others. Besides, in the classic scheme one can get from any station to any other one along the passages. The passages can be used to move in both directions. Between each pair of stations there is no more than one passage.

Berland mathematicians have recently proved a theorem that states that any classic scheme has a ringroad. There can be only one ringroad. In other words, in any classic scheme one can find the only scheme consisting of stations (where any two neighbouring ones are linked by a passage) and this cycle doesn't contain any station more than once.

This invention had a powerful social impact as now the stations could be compared according to their distance from the ringroad. For example, a citizen could say "I live in three passages from the ringroad" and another one could reply "you loser, I live in one passage from the ringroad". The Internet soon got filled with applications that promised to count the distance from the station to the ringroad (send a text message to a short number...).

The Berland government decided to put an end to these disturbances and start to control the situation. You are requested to write a program that can determine the remoteness from the ringroad for each station by the city subway scheme.

Input

The first line contains an integer n (3 ≤ n ≤ 3000), n is the number of stations (and trains at the same time) in the subway scheme. Then n lines contain descriptions of the trains, one per line. Each line contains a pair of integers xi, yi (1 ≤ xi, yi ≤ n) and represents the presence of a passage from station xi to station yi. The stations are numbered from 1 to n in an arbitrary order. It is guaranteed that xi ≠ yi and that no pair of stations contain more than one passage. The passages can be used to travel both ways. It is guaranteed that the given description represents a classic subway scheme.

Output

Print n numbers. Separate the numbers by spaces, the i-th one should be equal to the distance of the i-th station from the ringroad. For the ringroad stations print number 0.

Examples

Input

4
1 3
4 3
4 2
1 2


Output

0 0 0 0 

Input

6
1 2
3 4
6 4
2 3
1 3
3 5


Output

0 0 0 1 1 2

Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Graph traversal

Starter code:

Solutions:
import sys
from collections import deque
sys.setrecursionlimit(30000)
sz = 3333
cyclic = 0
begin = 0
end = 0
cycle = []
graph = []
used = []
parent = []
dist = []

def dfs(current, prev):
	global graph, begin, end, used, parent
	used[current] = 1
	for nxt in graph[current]:
		if used[nxt] != 2 and nxt != prev:
			if used[nxt] == 0:
				parent[current] = nxt
				if dfs(nxt, current):
					return True
			elif used[nxt] == 1:
				begin = current
				end = nxt
				return True
	used[current] = 2
	return False

def other_dfs(graph, current, cycle_in, d):
	used[current] = 1
	global dist
	dist[current] = 0 if cycle_in[current] else d
	d = dist[current]
	for nxt in graph[current]:
		if not used[nxt]:
			other_dfs(graph, nxt, cycle_in, d + 1)

def main():
	n = int(input())
	global graph, used, parent, dist
	cycle = []
	graph = [[] for i in range(sz)]
	used = [0 for i in range(sz)]
	parent = [0 for i in range(sz)]
	dist = [0 for i in range(sz)]
	for i in range(n):
		(x, y) = [int(i) for i in input().split()]
		graph[x - 1].append(y - 1)
		graph[y - 1].append(x - 1)
	for i in range(n):
		if not used[i]:
			if dfs(i, -1):
				break
	u = end
	parent[begin] = -1
	while u != -1:
		cycle.append(u)
		u = parent[u]
	cycle_in = [False for i in range(n)]
	for node in cycle:
		cycle_in[node] = True
	used = [0 for i in range(n)]
	other_dfs(graph, begin, cycle_in, 0)
	for node in dist[:n]:
		print(node, end=' ')
main()


from queue import Queue
from copy import deepcopy
BigNum = 10 ** 10
n = int(input())
vs = [set() for i in range(n + 1)]
for i in range(n):
	(x, y) = map(int, input().split(' '))
	vs[x].add(y)
	vs[y].add(x)
vsOriginal = deepcopy(vs)
removed = [False] * (n + 1)
q = Queue()
for i in range(1, n + 1):
	if len(vs[i]) == 1:
		q.put(i)
		removed[i] = True
while not q.empty():
	v = q.get()
	for nex in vs[v]:
		vs[nex].discard(v)
		if len(vs[nex]) <= 1 and (not removed[nex]):
			removed[nex] = True
			q.put(nex)
vs = vsOriginal
q = Queue()
ds = [BigNum] * (n + 1)
for i in range(1, n + 1):
	if not removed[i]:
		q.put((i, 0))
		ds[i] = 0
while not q.empty():
	(v, dist) = q.get()
	for nex in vs[v]:
		if ds[nex] == BigNum:
			q.put((nex, dist + 1))
			ds[nex] = dist + 1
print(*ds[1:])


def dfs_non_recursive(graph, source):
	path = []
	stack = [source]
	fathers = [x for x in range(len(graph))]
	cycle = [0 for x in range(len(graph))]
	while len(stack) != 0:
		v = stack.pop()
		if v not in path:
			path.append(v)
		for w in range(len(graph)):
			if graph[v][w]:
				if fathers[v] == w:
					continue
				if w in path:
					start = w
					end = v
					current = end
					while current != start:
						cycle[current] = 1
						current = fathers[current]
					cycle[current] = 1
					return cycle
				else:
					fathers[w] = v
					stack.append(w)
	return 0

def solve(graph):
	n = len(graph)
	fathers = [x for x in range(n)]
	mark = [0 for x in range(n)]
	cycle = dfs_non_recursive(graph, 0)
	result = [0 for x in range(n)]
	for i in range(n):
		if cycle[i] == 1:
			tmp = getDistances(graph, i, cycle)
			for i in range(n):
				if tmp[i] != -1:
					result[i] = tmp[i]
	return result

def getDistances(graph, source, cycle):
	stack = [source]
	d = [-1 for x in range(len(graph))]
	d[source] = 0
	for i in range(len(cycle)):
		if cycle[i] == 1:
			d[i] = 0
	while len(stack) != 0:
		v = stack.pop()
		for w in range(len(graph)):
			if graph[v][w] and d[w] == -1:
				d[w] = d[v] + 1
				stack.append(w)
	return d
n = int(input())
graph = [[0 for x in range(n)] for x in range(n)]
for item in range(n):
	(u, v) = map(int, input().split())
	graph[u - 1][v - 1] = 1
	graph[v - 1][u - 1] = 1
result = solve(graph)
tmp = str(result[0])
for i in range(1, n):
	tmp += ' ' + str(result[i])
print(tmp)


from sys import setrecursionlimit
setrecursionlimit(30000)

def cycle(f):
	v = f
	cyc[v] = True
	v = p[v]
	while v != f:
		cyc[v] = True
		v = p[v]

def dfs(v, par):
	global c, p, cycleroot
	if c[v] == 2:
		return
	p[v] = par
	if c[v] == 1:
		cycle(v)
		cycleroot = v
		return True
	c[v] = 1
	for u in graph[v]:
		if u != par:
			if dfs(u, v):
				return True
	c[v] = 2
	return False

def dfs1(v, d):
	if used[v]:
		return
	used[v] = True
	if cyc[v]:
		dist[v] = 0
	else:
		dist[v] = d
	for u in graph[v]:
		dfs1(u, dist[v] + 1)
n = int(input())
m = n
graph = [[] for i in range(n)]
p = [-1] * n
c = [0] * n
cyc = [False] * n
if m != n:
	print('NO')
	exit(0)
for i in range(m):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	graph[a].append(b)
	graph[b].append(a)
dfs(0, -1)
used = [False] * n
dist = [-1] * n
dfs1(cycleroot, 0)
print(' '.join([str(i) for i in dist]))


from collections import deque
import sys
sys.setrecursionlimit(5000)

class Graph(object):

	def __init__(self, vertices, adj):
		self.vertices = vertices
		self.dist = self.init_dist(vertices)
		self.adj = adj

	def init_dist(self, v):
		d = {}
		for i in range(1, v + 1):
			d[i] = 0
		return d

	def iter_vertices(self):
		for v in range(1, self.vertices + 1):
			yield v

	def adj_list(self, v):
		return self.adj[v]

class dfs_result:

	def __init__(self):
		self.dist = {}
		self.parent = {}
		self.finish_time = {}
		self.start_time = {}
		self.edges = {}
		self.order = []
		self.t = 0
		self.loop = None

def dfs(g):
	result = dfs_result()
	for vertex in g.iter_vertices():
		if vertex not in result.parent:
			dfs_visit(g, vertex, result)
	return result

def dfs_visit(g, v, result, parent=None):
	result.parent[v] = parent
	result.t += 1
	result.start_time[v] = result.t
	if parent:
		result.edges[parent, v] = 'tree'
	for n in g.adj_list(v):
		if n not in result.parent:
			dfs_visit(g, n, result, v)
		elif n not in result.finish_time:
			if (n, v) not in result.edges:
				result.edges[v, n] = 'back'
				result.loop = [v, n]
		elif result.start_time[v] < result.finish_time[n]:
			result.edges[v, n] = 'forward'
		else:
			result.edges[v, n] = 'cross'
	result.t += 1
	result.finish_time[v] = result.t
	result.order.append(v)

class BFSResult:

	def __init__(self):
		self.level = {}
		self.parent = {}

def bfs(g, r, loop_dict, s):
	r.parent = {s: None}
	r.level = {s: 0}
	queue = deque()
	queue.append(s)
	while queue:
		u = queue.popleft()
		for n in g.adj_list(u):
			if n not in r.level and n not in loop_dict:
				r.parent[n] = u
				r.level[n] = r.level[u] + 1
				g.dist[n] = r.level[n]
				queue.append(n)
t = int(input().rstrip())
adj = {}
for i in range(t):
	(u, v) = list(map(int, input().rstrip().split()))
	try:
		adj[u].append(v)
	except KeyError:
		adj[u] = [v]
	try:
		adj[v].append(u)
	except KeyError:
		adj[v] = [u]
g = Graph(t, adj)
r = dfs(g)
start = r.loop[1]
end = r.loop[0]
loop = [end]
loop_dict = {end: 1}
while r.parent[end] != start:
	loop.append(r.parent[end])
	loop_dict[r.parent[end]] = 1
	end = r.parent[end]
loop.append(start)
loop_dict[start] = 1
br = BFSResult()
for s in loop:
	bfs(g, br, loop_dict, s)
d = g.dist
for k in d:
	print(d[k], end=' ')


from collections import *
read_line = lambda : [int(i) for i in input().split(' ')]
n = read_line()[0]
(g, deg) = ([[] for i in range(n)], [0] * n)
for i in range(n):
	(a, b) = [v - 1 for v in read_line()]
	g[a].append(b)
	g[b].append(a)
	deg[a] += 1
	deg[b] += 1
ans = [0] * n
q = deque((v for v in range(n) if deg[v] == 1))
while q:
	v = q.popleft()
	ans[v] = None
	for u in g[v]:
		deg[u] -= 1
		if deg[u] == 1:
			q.append(u)
q = deque((v for v in range(n) if ans[v] == 0))
while q:
	v = q.popleft()
	for u in g[v]:
		if ans[u] is None:
			ans[u] = ans[v] + 1
			q.append(u)
print(' '.join((str(x) for x in ans)))


__author__ = 'artyom'
read = lambda : map(int, input().split())
n = int(input())
graph = [set() for _ in range(n + 1)]
for __ in range(n):
	(u, v) = read()
	graph[u].add(v)
	graph[v].add(u)

def dfs(start):
	(parents, stack) = ([0] * (n + 1), [(start, -1)])
	while stack:
		(vertex, parent) = stack.pop()
		parents[vertex] = parent
		for neighbour in graph[vertex]:
			if neighbour != parent:
				if parents[neighbour]:
					cycle = set()
					cycle.add(neighbour)
					while vertex != neighbour:
						cycle.add(vertex)
						vertex = parents[vertex]
					return cycle
				stack.append((neighbour, vertex))
ring = dfs(1)

def bfs():
	levels = [0] * (n + 1)
	visited = set(ring)
	for start in ring:
		frontier = set()
		frontier.add(start)
		level = 0
		while frontier:
			next_frontier = set()
			for vertex in frontier:
				levels[vertex] = level
				visited.add(vertex)
				next_frontier |= graph[vertex] - visited
			frontier = next_frontier
			level += 1
	return levels
print(' '.join(map(str, bfs()[1:])))


import sys
import math
n = int(input())
e = [[] for _ in range(n)]
for _ in range(n):
	(x, y) = map(int, input().split())
	e[x - 1].append(y - 1)
	e[y - 1].append(x - 1)
d = [len(x) for x in e]
q = [i for i in range(n) if d[i] == 1]
c = [0] * n
for u in q:
	c[u] = n
	for v in e[u]:
		d[v] -= 1
		if d[v] == 1:
			q.append(v)
q.extend((i for i in range(n) if not c[i]))
for u in q[::-1]:
	for v in e[u]:
		c[v] = min(c[v], c[u] + 1)
print(' '.join(map(str, c)))


from collections import deque

def findCycle(grafo):
	n = len(grafo)
	cantidad_conexiones = [len(destinos) for destinos in grafo]
	visitados = [False for i in range(n)]
	cola = deque((i for i in range(n) if cantidad_conexiones[i] == 1))
	while cola:
		while cola:
			nodo = cola.popleft()
			visitados[nodo] = True
			for destino in grafo[nodo]:
				cantidad_conexiones[destino] -= 1
		cola = deque((i for i in range(n) if cantidad_conexiones[i] == 1 and (not visitados[i])))
	nodos_ciclo = []
	for i in range(n):
		if not visitados[i]:
			nodos_ciclo.append(i)
	return nodos_ciclo

def distanciasAlCiclo(grafo, ciclo, numero_grande=float('inf')):
	distancias = [numero_grande for i in range(n)]
	for nodo in ciclo:
		distancias[nodo] = 0
	cola = deque(ciclo)
	while len(cola):
		nodo = cola.popleft()
		for conectado in grafo[nodo]:
			if distancias[conectado] == numero_grande:
				distancias[conectado] = distancias[nodo] + 1
				if conectado not in ciclo:
					cola.append(conectado)
	return distancias
n = int(input())
grafo = [list() for i in range(n)]
for i in range(n):
	(x, y) = map(lambda z: int(z) - 1, input().split())
	grafo[x].append(y)
	grafo[y].append(x)
nodos_ciclo = findCycle(grafo)
print(' '.join(map(str, distanciasAlCiclo(grafo, nodos_ciclo))))


from collections import deque

def findCycle(grafo):
	n = len(grafo)
	degree = dict()
	for i in range(n):
		degree[i] = len(grafo[i])
	visited = [False for i in range(n)]
	q = deque()
	while True:
		for i in range(len(degree)):
			if degree[i] == 1 and visited[i] == False:
				q.append(i)
		if len(q) == 0:
			break
		while q:
			temp = q.popleft()
			visited[temp] = True
			for destino in grafo[temp]:
				degree[destino] -= 1
	result = []
	for i in range(len(visited)):
		if visited[i] == False:
			result.append(i)
	return result

def distanciasAlCiclo(grafo, ciclo, numero_grande=float('inf')):
	distancias = [numero_grande for i in range(n)]
	for nodo in ciclo:
		distancias[nodo] = 0
	cola = deque(ciclo)
	while len(cola):
		nodo = cola.popleft()
		for conectado in grafo[nodo]:
			if distancias[conectado] == numero_grande:
				distancias[conectado] = distancias[nodo] + 1
				cola.append(conectado)
	return distancias
n = int(input())
grafo = [list() for i in range(n)]
for i in range(n):
	(x, y) = map(lambda z: int(z) - 1, input().split())
	grafo[x].append(y)
	grafo[y].append(x)
nodos_ciclo = findCycle(grafo)
print(' '.join(map(str, distanciasAlCiclo(grafo, nodos_ciclo))))


from collections import defaultdict, deque

def nodeInCycle(graph, n):
	global time
	nodesInCycle = []
	arrivalTime = [0] + [float('inf') for _ in range(n)]

	def dfs(node, parent):
		global time
		if arrivalTime[node] != float('inf'):
			return arrivalTime[node]
		arrivalTime[node] = time
		minArrival = float('inf')
		for child in graph.get(node, set()):
			if child != parent:
				time += 1
				minArrival = min(dfs(child, node), minArrival)
		if minArrival <= arrivalTime[node]:
			nodesInCycle.append(node)
			arrivalTime[node] = minArrival
		return arrivalTime[node]
	dfs(1, None)
	return nodesInCycle

def distanceFromRing(graph, n):
	nodesInCycle = nodeInCycle(graph, n)
	distance = [0] + [float('inf') for _ in range(1, n + 1)]
	for node in nodesInCycle:
		distance[node] = 0
	queue = deque([(node, 0) for node in nodesInCycle])
	while queue:
		(node, distFromRing) = queue.popleft()
		for child in graph.get(node, set()):
			if distance[child] == float('inf'):
				distance[child] = distFromRing + 1
				queue.append((child, distance[child]))
	return distance

def main(edges, n):
	graph = defaultdict(set)
	for (u, v) in edges:
		graph[u].add(v)
		graph[v].add(u)
	return distanceFromRing(graph, n)[1:]
import sys
sys.setrecursionlimit(10000)
n = int(input())
edges = []
time = 1
for _ in range(n):
	(u, v) = tuple(map(int, input().split()))
	edges.append((u, v))
print(*main(edges, n))


import bisect
n = int(input())
g = [[] for i in range(n)]
for i in range(n):
	(u, v) = map(int, input().split())
	g[u - 1].append(v - 1)
	g[v - 1].append(u - 1)
d = [len(x) for x in g]
q = [i for i in range(n) if d[i] == 1]
c = [0] * n
for u in q:
	c[u] = n
	for v in g[u]:
		d[v] -= 1
		if d[v] == 1:
			q.append(v)
q.extend((i for i in range(n) if not c[i]))
for u in q[::-1]:
	for v in g[u]:
		c[v] = min(c[v], c[u] + 1)
print(*c)


from sys import stdin, stderr
from collections import defaultdict

def readInts():
	return map(int, stdin.readline().strip().split())

def print_err(*args, **kwargs):
	print(*args, file=stderr, **kwargs)

def find_cycle(g):
	path = [None, 1]
	path_set = set(path)
	s = [(path, path_set)]
	while s:
		(path, path_set) = s.pop()
		node = path[-1]
		parent = path[-2]
		for nn in g[node]:
			if nn == parent:
				continue
			if nn in path_set:
				out = []
				while path:
					out.append(path.pop())
					if nn == out[-1]:
						return out
			path_set2 = set(path_set)
			path2 = list(path)
			path_set2.add(nn)
			path2.append(nn)
			s.append((path2, path_set2))
	return None

def find_dists(n, g, ring):
	dists = [0 for _ in range(n + 1)]
	fringe = set(ring)
	disc = set(ring)
	d = 0
	while fringe:
		fringe_next = set()
		for n in fringe:
			dists[n] = d
			for nn in g[n]:
				if nn in disc:
					continue
				fringe_next.add(nn)
		disc = disc.union(fringe_next)
		fringe = fringe_next
		d += 1
	return dists

def solve(n, g):
	ring = find_cycle(g)
	dists = find_dists(n, g, ring)
	return dists

def run():
	(n,) = readInts()
	g = defaultdict(list)
	for _ in range(n):
		(a, b) = readInts()
		g[a].append(b)
		g[b].append(a)
	vs = solve(n, g)[1:]
	print(' '.join(map(str, vs)))
run()


def solve(graph):
	n = len(graph)
	cycle = getCycle(graph)
	result = [0 for x in range(n)]
	for i in range(n):
		if cycle[i] == 1:
			result[i] = 0
			continue
		result[i] = getDistance(graph, i, cycle)
	return result

def getCycle(graph):
	n = len(graph)
	mark = [0 for x in range(n)]
	fathers = [x for x in range(len(graph))]
	cycle = [0 for x in range(len(graph))]
	stack = [0]
	while len(stack) > 0:
		v = stack.pop()
		mark[v] = 1
		for w in graph[v]:
			if fathers[v] == w:
				continue
			if mark[w]:
				start = w
				end = v
				current = end
				while current != start:
					cycle[current] = 1
					current = fathers[current]
				cycle[current] = 1
				return cycle
			else:
				fathers[w] = v
				stack.append(w)

def getDistance(graph, source, cycle):
	stack = [source]
	d = [-1 for x in range(len(graph))]
	d[source] = 0
	while len(stack) != 0:
		v = stack.pop()
		for w in graph[v]:
			if cycle[w] == 1:
				return d[v] + 1
			elif d[w] == -1:
				d[w] = d[v] + 1
				stack.append(w)
n = int(input())
graph = [[] for x in range(n)]
for item in range(n):
	(u, v) = map(int, input().split())
	graph[u - 1].append(v - 1)
	graph[v - 1].append(u - 1)
result = solve(graph)
tmp = str(result[0])
for i in range(1, n):
	tmp += ' ' + str(result[i])
print(tmp)


n = int(input())
(t, p) = ([0] * (n + 1), [[] for i in range(n + 1)])
for i in range(n):
	(a, b) = map(int, input().split())
	p[a].append(b)
	p[b].append(a)
(q, x, y) = ([1], 0, 0)
while not x:
	i = q.pop()
	for j in p[i]:
		if t[i] == j:
			continue
		if t[j]:
			(t[j], x, y) = (i, j, t[j])
			break
		t[j] = i
		q.append(j)
r = [y]
while x != y:
	r.append(x)
	x = t[x]
t = [-1] * (n + 1)
for i in r:
	t[i] = 0
for k in r:
	q = [j for j in p[k] if t[j]]
	for i in q:
		t[i] = 1
	while q:
		i = q.pop()
		for j in p[i]:
			if t[j] < 0:
				t[j] = t[i] + 1
				q.append(j)
print(' '.join(map(str, t[1:])))


from sys import setrecursionlimit
setrecursionlimit(30000)
n = int(input())
A = [[] for i in range(n + 1)]
visited = [0 for i in range(n + 1)]
for i in range(n):
	(u, v) = map(int, input().split())
	A[u].append(v)
	A[v].append(u)
ring = []
prev = [0 for i in range(n + 1)]
grey = [0 for i in range(n + 1)]
black = [0 for i in range(n + 1)]

def dfs(u):
	if len(ring) != 0:
		return
	visited[u] = 1
	grey[u] = 1
	for i in A[u]:
		if visited[i] == 1:
			if grey[i] == 1 and prev[u] != i:
				x = u
				while x != i:
					ring.append(x)
					x = prev[x]
				ring.append(i)
				grey[u] = 0
				black[u] = 1
				return
		else:
			prev[i] = u
			dfs(i)
	grey[u] = 0
	black[u] = 1
	return
dfs(1)
visited = [0 for i in range(n + 1)]
ans = [None for i in range(n + 1)]

def dfs1(u, d):
	k = 0
	visited[u] = 1
	if u in ring:
		ans[u] = 0
	else:
		ans[u] = d
	for i in A[u]:
		if visited[i] == 0:
			dfs1(i, ans[u] + 1)
dfs1(ring[0], 0)
print(' '.join(map(str, ans[1:])))