Doubly linked list is one of the fundamental data structures. A doubly linked list is a sequence of elements, each containing information about the previous and the next elements of the list. In this problem all lists have linear structure. I.e. each element except the first has exactly one previous element, each element except the last has exactly one next element. The list is not closed in a cycle.

In this problem you are given n memory cells forming one or more doubly linked lists. Each cell contains information about element from some list. Memory cells are numbered from 1 to n.

For each cell i you are given two values:   l_{i} — cell containing previous element for the element in the cell i;  r_{i} — cell containing next element for the element in the cell i. 

If cell i contains information about the element which has no previous element then l_{i} = 0. Similarly, if cell i contains information about the element which has no next element then r_{i} = 0. [Image] Three lists are shown on the picture. 

For example, for the picture above the values of l and r are the following: l_1 = 4, r_1 = 7; l_2 = 5, r_2 = 0; l_3 = 0, r_3 = 0; l_4 = 6, r_4 = 1; l_5 = 0, r_5 = 2; l_6 = 0, r_6 = 4; l_7 = 1, r_7 = 0.

Your task is to unite all given lists in a single list, joining them to each other in any order. In particular, if the input data already contains a single list, then there is no need to perform any actions. Print the resulting list in the form of values l_{i}, r_{i}.

Any other action, other than joining the beginning of one list to the end of another, can not be performed.


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 100) — the number of memory cells where the doubly linked lists are located.

Each of the following n lines contains two integers l_{i}, r_{i} (0 ≤ l_{i}, r_{i} ≤ n) — the cells of the previous and the next element of list for cell i. Value l_{i} = 0 if element in cell i has no previous element in its list. Value r_{i} = 0 if element in cell i has no next element in its list.

It is guaranteed that the input contains the correct description of a single or more doubly linked lists. All lists have linear structure: each element of list except the first has exactly one previous element; each element of list except the last has exactly one next element. Each memory cell contains information about one element from some list, each element of each list written in one of n given cells.


-----Output-----

Print n lines, the i-th line must contain two integers l_{i} and r_{i} — the cells of the previous and the next element of list for cell i after all lists from the input are united in a single list. If there are many solutions print any of them.


-----Example-----
Input
7
4 7
5 0
0 0
6 1
0 2
0 4
1 0

Output
4 7
5 6
0 5
6 1
3 2
2 4
1 0

Source: codeforces | Difficulty: MEDIUM
Tags: Implementation


Solutions:
import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
from collections import defaultdict
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 = int(input())
A = [list(map(int, input().split())) for i in range(n)]
start = []
end = []
for i in range(n):
	if A[i][0] == 0:
		start.append(i)
	elif A[i][1] == 0:
		end.append(i)
for curr in range(len(start)):
	x = start[curr]
	while A[x][1] != 0:
		x = A[x][1] - 1
	if curr != len(start) - 1:
		A[x][1] = start[curr + 1] + 1
		A[A[x][1] - 1][0] = x + 1
for i in range(n):
	print(A[i][0], A[i][1])


def run(i):
	global l
	d[i] = 1
	if l[i][1] == 0:
		return i
	return run(l[i][1])
n = int(input())
l = []
for u in range(n):
	l.append(list(map(int, input().split())))
l.insert(0, 0)
d = {}
ans = 0
start = 0
for i in range(1, len(l)):
	if l[i][0] == 0:
		ans = run(i)
		start = i
		break
for i in range(start + 1, len(l)):
	if l[i][0] == 0:
		l[i][0] = ans
		l[ans][1] = i
		ans = run(i)
for val in range(1, len(l)):
	print(l[val][0], l[val][1])


l = []
l2 = []
r2 = []
r = []
a = []
u = 0
q = 0
p = 0
n = int(input())
for i in range(n):
	(x1, x2) = map(int, input().split())
	l.append(x1)
	r.append(x2)
	if x1 == 0:
		u = u + 1
for i2 in range(u):
	y = 0
	for i in range(p, n):
		if l[i] == 0 and y == 0:
			a.append(i + 1)
			y = 1
			q = i
			p = i + 1
	while r[q] != 0:
		a.append(r[q])
		q = r[q] - 1
for i3 in range(n + 1):
	l2.append(0)
for i3 in range(1, n):
	l2[a[i3]] = a[i3 - 1]
del l2[0]
for i3 in range(n + 1):
	r2.append(0)
for i3 in range(0, n - 1):
	r2[a[i3]] = a[i3 + 1]
del r2[0]
for i3 in range(n):
	print(l2[i3], r2[i3])


class CodeforcesTask847ASolution:

	def __init__(self):
		self.result = ''
		self.n = 0
		self.cells = []

	def read_input(self):
		self.n = int(input())
		for x in range(self.n):
			self.cells.append([int(y) for y in input().split(' ')])

	def process_task(self):
		lists = []
		for x in range(self.n):
			if not self.cells[x][0]:
				nc = [x + 1]
				curr = x
				while self.cells[curr][1]:
					curr = self.cells[curr][1] - 1
				nc.append(curr + 1)
				lists.append(nc)
		for x in range(len(lists) - 1):
			self.cells[lists[x][1] - 1][1] = lists[x + 1][0]
			self.cells[lists[x + 1][0] - 1][0] = lists[x][1]
		self.result = '\n'.join(['{0} {1}'.format(*cell) for cell in self.cells])

	def get_result(self):
		return self.result

def __starting_point():
	Solution = CodeforcesTask847ASolution()
	Solution.read_input()
	Solution.process_task()
	print(Solution.get_result())
__starting_point()


n = int(input())
starts = dict()
ends = dict()
start_points = set()
for i in range(n):
	(st, en) = map(int, input().split())
	if st == 0:
		start_points.add(i + 1)
	starts[i + 1] = st
	ends[i + 1] = en
lists = []
it = iter(start_points)
x = next(it)
while ends[x] != 0:
	x = ends[x]
for st in it:
	starts[st] = x
	ends[x] = st
	while ends[x] != 0:
		x = ends[x]
for i in range(1, n + 1):
	print(starts[i], ends[i], sep=' ')


nodes = []
start_nodes = []
for i in range(int(input().strip())):
	(left, right) = input().strip().split()
	left = int(left)
	right = int(right)
	current = i + 1
	if left == 0:
		start_nodes.append([left, current, right])
	else:
		nodes.append([left, current, right])
lists = []
for node in start_nodes:
	links = [node]
	while True:
		prevlen = len(links)
		for i in range(len(nodes)):
			if links[-1][-1] == nodes[i][1]:
				links.append(nodes[i])
		nextlen = len(links)
		if prevlen == nextlen:
			break
	lists.append(links)
flattened = [node for ll in lists for node in ll]
for i in range(1, len(flattened)):
	if flattened[i][0] == 0:
		flattened[i][0] = flattened[i - 1][1]
		flattened[i - 1][2] = flattened[i][1]
sorted_union = sorted(flattened, key=lambda x: x[1])
for node in sorted_union:
	print(node[0], node[2])


import sys
import math
data = sys.stdin.read().split()
data_ptr = 0

def data_next():
	global data_ptr, data
	data_ptr += 1
	return data[data_ptr - 1]
N = int(data_next())
pre = [0] + list(map(int, data[1::2]))
nxt = [0] + list(map(int, data[2::2]))
vis = [False] * (N + 1)

def find_last(u, nxt):
	while nxt[u] != 0:
		u = nxt[u]
		vis[u] = True
	return u
pre_last = -1
for i in range(1, N + 1):
	if not vis[i]:
		vis[i] = True
		first = find_last(i, pre)
		last = find_last(i, nxt)
		if pre_last != -1:
			nxt[pre_last] = first
			pre[first] = pre_last
		pre_last = last
for i in range(1, N + 1):
	print(pre[i], nxt[i])


n = int(input())
arr = []
for i in range(n):
	(l, r) = map(int, input().split())
	arr.append([l, r])
lts = []
for i in range(n):
	if arr[i][0] == 0:
		l = i
		j = i
		while arr[j][1] != 0:
			j = arr[j][1] - 1
		r = j
		lts.append([l, r])
for i in range(1, len(lts)):
	arr[lts[i - 1][1]][1] = lts[i][0] + 1
	arr[lts[i][0]][0] = lts[i - 1][1] + 1
for i in range(n):
	print(arr[i][0], arr[i][1])


n = int(input())
dl = [[0, 0]]
end = 0
for i in range(n):
	dl.append(list(map(int, input().split())))
for i in range(1, n + 1):
	if not dl[i][0]:
		dl[end][1] = i
		dl[i][0] = end
		j = i
		while dl[j][1]:
			j = dl[j][1]
		end = j
for node in dl[1:]:
	print(*node)


n = int(input())
if n == 1:
	print(0, 0)
	return
a = []
for i in range(n):
	a.append(list(map(int, input().split())))
s = []
i = 0
while i < n:
	if a[i][0] == 0:
		k = i
		s.append([i + 1])
		while a[k][1] != 0:
			k = a[k][1] - 1
			s[-1].append(k + 1)
	i += 1
p = []
for i in s:
	p.extend(i)
for i in range(n):
	if i == 0:
		a[p[i] - 1] = [0, p[1]]
	elif i == n - 1:
		a[p[i] - 1] = [p[i - 1], 0]
	else:
		a[p[i] - 1] = [p[i - 1], p[i + 1]]
for i in a:
	print(i[0], i[1])


n = int(input())
A = [list(map(int, input().split())) for i in range(n)]
start = []
end = []
for i in range(n):
	if A[i][0] == 0:
		start.append(i)
	elif A[i][1] == 0:
		end.append(i)
for curr in range(len(start)):
	x = start[curr]
	while A[x][1] != 0:
		x = A[x][1] - 1
	if curr != len(start) - 1:
		A[x][1] = start[curr + 1] + 1
		A[A[x][1] - 1][0] = x + 1
for i in range(n):
	print(A[i][0], A[i][1])


import sys
input = sys.stdin.readline
from collections import defaultdict
n = int(input())
left = [-1 for _ in range(n + 1)]
right = [-1 for _ in range(n + 1)]
cannot = defaultdict(int)
for x in range(1, n + 1):
	(l, r) = map(int, input().split())
	left[x] = l
	right[x] = r
for i in range(1, n + 1):
	if left[i] == 0:
		x = i
		while right[x] != 0:
			x = right[x]
		cannot[i] = x
for i in range(1, n + 1):
	if left.count(0) == 1:
		break
	if left[i] == 0:
		for j in range(1, n + 1):
			if right[j] == 0 and cannot[i] != j:
				left[i] = j
				right[j] = i
				cannot.clear()
				for i in range(1, n + 1):
					if left[i] == 0:
						x = i
						while right[x] != 0:
							x = right[x]
						cannot[i] = x
				break
for i in range(1, n + 1):
	print(left[i], right[i])


n = int(input())
ll = [list(map(int, input().split())) for _ in range(n)]
ll = [[0, 0]] + ll
tail = 0
visited = [False] * (n + 1)
cnt = 0
while cnt < n:
	for i in range(1, n + 1):
		if ll[i][0] == 0 and (not visited[i]):
			head = i
			visited[head] = True
			cnt += 1
			break
	ll[tail][1] = head
	ll[head][0] = tail
	while ll[head][1] != 0:
		head = ll[head][1]
		visited[head] = True
		cnt += 1
	tail = head
for i in range(1, n + 1):
	print(ll[i][0], ll[i][1])


(k, n) = (0, int(input()))
t = [list(map(int, input().split())) for j in range(n)]
for (m, (l, r)) in enumerate(t, 1):
	if not l:
		if k:
			(t[k - 1][1], t[m - 1][0]) = (m, k)
		k = m
		while r:
			(k, r) = (r, t[r - 1][1])
for (l, r) in t:
	print(l, r)


import os
import sys
from io import BytesIO, IOBase
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')
from math import gcd, ceil

def pre(s):
	n = len(s)
	pi = [0] * n
	for i in range(1, n):
		j = pi[i - 1]
		while j and s[i] != s[j]:
			j = pi[j - 1]
		if s[i] == s[j]:
			j += 1
		pi[i] = j
	return pi

def prod(a):
	ans = 1
	for each in a:
		ans = ans * each
	return ans

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def connected_components(n, graph):
	(components, visited) = ([], [False] * n)

	def dfs(start):
		(component, stack) = ([], [start])
		while stack:
			start = stack[-1]
			if visited[start]:
				stack.pop()
				continue
			else:
				visited[start] = True
				component.append(start)
			for i in graph[start]:
				if not visited[i]:
					stack.append(i)
		return component
	for i in range(n):
		if not visited[i]:
			components.append(dfs(i))
	return components
for _ in range(int(input()) if not True else 1):
	n = int(input())
	alpha = []
	a = []
	comps = 0
	for i in range(n):
		(x, y) = map(int, input().split())
		if not x:
			alpha += [i]
			comps += 1
		a += [[x, y]]
	for i in range(comps):
		x = alpha[i]
		while a[x][1]:
			x = a[x][1] - 1
		if i + 1 != len(alpha):
			y = alpha[i + 1]
			a[x][1] = y + 1
			a[y][0] = x + 1
	for each in a:
		print(*each)


n = int(input())
C = [0] * (n + 1)

def vis(i, label, L, R):
	if C[i] == 0:
		C[i] = label
		if L[i] != 0:
			vis(L[i], label, L, R)
		if R[i] != 0:
			vis(R[i], label, L, R)
L = [0] * (n + 1)
R = [0] * (n + 1)
label = 1
for i in range(1, n + 1):
	(l, r) = list(map(int, input().split()))
	L[i] = l
	R[i] = r
for i in range(1, n + 1):
	if C[i] == 0:
		vis(i, label, L, R)
		label += 1
label -= 1
for i in range(1, n + 1):
	if label == 1:
		break
	if L[i] != 0 and R[i] != 0:
		continue
	for j in range(1, n + 1):
		if i != j:
			if L[i] == 0 and R[j] == 0 and (C[i] != C[j]):
				L[i] = j
				R[j] = i
				target = C[j]
				newL = C[i]
				for k in range(1, n + 1):
					if C[k] == target:
						C[k] = newL
				label -= 1
			elif R[i] == 0 and L[j] == 0 and (C[i] != C[j]):
				R[i] = j
				L[j] = i
				target = C[j]
				newL = C[i]
				for k in range(1, n + 1):
					if C[k] == target:
						C[k] = newL
				label -= 1
for i in range(1, n + 1):
	print(str(L[i]) + ' ' + str(R[i]))


n = int(input())
(l, r) = ([0] * n, [0] * n)
for i in range(n):
	(l[i], r[i]) = map(int, input().split())
arr = []
used = [0] * n
for it in range(1000):
	a = -1
	for i in range(n):
		if not used[i] and l[i] == 0:
			a = i
	while a != -1:
		used[a] = 1
		arr.append(a)
		a = r[a] - 1
l[arr[0]] = 0
r[arr[-1]] = 0
for i in range(n - 1):
	l[arr[i + 1]] = arr[i] + 1
	r[arr[i]] = arr[i + 1] + 1
for i in range(n):
	print(l[i], r[i])


n = int(input())
(L, R) = ([], [])
(zL, zR) = ([], [])
A = []
for i in range(1, n + 1):
	(l, r) = map(int, input().split())
	if l == 0 and r == 0:
		A.append(i)
	elif l == 0:
		zL.append(i)
	elif r == 0:
		zR.append(i)
	L.append(l)
	R.append(r)
for i in zL:
	A.append(i)
	while R[i - 1] != 0:
		A.append(R[i - 1])
		i = R[i - 1]
for i in range(1, n + 1):
	index = A.index(i)
	if index == 0:
		a = 0
	else:
		a = A[max(0, index - 1)]
	if index == len(A) - 1:
		b = 0
	else:
		b = A[min(len(A) - 1, index + 1)]
	print(a, b)


from collections import defaultdict
n = int(input())
left_child = [0 for i in range(n + 1)]
right_child = [0 for i in range(n + 1)]
vis = [0 for i in range(n + 1)]
for i in range(n):
	(l, r) = map(int, input().split())
	left_child[i + 1] = l
	right_child[i + 1] = r
(left, right) = (1, 1)
while True:
	if left == 0:
		break
	vis[left] = 1
	left = left_child[left]
while True:
	if right == 0:
		break
	vis[right] = 1
	extend_node = right
	right = right_child[right]
for i in range(1, n + 1):
	if not vis[i]:
		(left, right) = (i, i)
		while True:
			if left == 0:
				break
			vis[left] = 1
			connect_node = left
			left = left_child[left]
		right_child[extend_node] = connect_node
		left_child[connect_node] = extend_node
		while True:
			if right == 0:
				break
			vis[right] = 1
			extend_node = right
			right = right_child[right]
for i in range(n):
	print(left_child[i + 1], right_child[i + 1])