A tree is an undirected connected graph without cycles.

Let's consider a rooted undirected tree with n vertices, numbered 1 through n. There are many ways to represent such a tree. One way is to create an array with n integers p_1, p_2, ..., p_{n}, where p_{i} denotes a parent of vertex i (here, for convenience a root is considered its own parent). [Image] For this rooted tree the array p is [2, 3, 3, 2]. 

Given a sequence p_1, p_2, ..., p_{n}, one is able to restore a tree:  There must be exactly one index r that p_{r} = r. A vertex r is a root of the tree.  For all other n - 1 vertices i, there is an edge between vertex i and vertex p_{i}. 

A sequence p_1, p_2, ..., p_{n} is called valid if the described procedure generates some (any) rooted tree. For example, for n = 3 sequences (1,2,2), (2,3,1) and (2,1,3) are not valid.

You are given a sequence a_1, a_2, ..., a_{n}, not necessarily valid. Your task is to change the minimum number of elements, in order to get a valid sequence. Print the minimum number of changes and an example of a valid sequence after that number of changes. If there are many valid sequences achievable in the minimum number of changes, print any of them.


-----Input-----

The first line of the input contains an integer n (2 ≤ n ≤ 200 000) — the number of vertices in the tree.

The second line contains n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ n).


-----Output-----

In the first line print the minimum number of elements to change, in order to get a valid sequence.

In the second line, print any valid sequence possible to get from (a_1, a_2, ..., a_{n}) in the minimum number of changes. If there are many such sequences, any of them will be accepted.


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

Output
1
2 3 4 4 

Input
5
3 2 2 5 3

Output
0
3 2 2 5 3 

Input
8
2 3 5 4 1 6 6 7

Output
2
2 3 7 8 1 6 6 7



-----Note-----

In the first sample, it's enough to change one element. In the provided output, a sequence represents a tree rooted in a vertex 4 (because p_4 = 4), which you can see on the left drawing below. One of other correct solutions would be a sequence 2 3 3 2, representing a tree rooted in vertex 3 (right drawing below). On both drawings, roots are painted red. [Image] 

In the second sample, the given sequence is already valid.

Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Graph traversal

Constructive algorithms

Tree algorithms

Spanning trees

Starter code:

Solutions:
input()
A = list(map(int, input().split(' ')))
root = -1
for (i, a) in enumerate(A):
	if i == a - 1:
		root = i
		break
v = [False] * len(A)
if root > -1:
	v[root] = True
changed = 0
for (i, a) in enumerate(A):
	if v[i]:
		continue
	v[i] = True
	l = [i]
	a -= 1
	while not v[a]:
		l.append(a)
		v[a] = True
		a = A[a] - 1
	if a in l:
		if root == -1:
			A[a] = a + 1
			root = a
			changed += 1
		else:
			A[a] = root + 1
			changed += 1
print(changed)
print(' '.join(map(str, A)))


n = int(input())
a = list(map(int, input().split()))
par = []
for i in range(n):
	if a[i] == i + 1:
		par.append(i)
v = [False for i in range(n)]
for i in par:
	v[i] = True
ccl = []
for i in range(n):
	if v[i]:
		continue
	s = [i]
	v[i] = True
	p = set(s)
	t = True
	while s and t:
		x = s.pop()
		j = a[x] - 1
		if j in p:
			ccl.append(j)
			t = False
		else:
			s.append(j)
			p.add(j)
		if v[j]:
			t = False
		else:
			v[j] = True
if len(par) == 0:
	print(len(ccl))
	c = ccl[0]
	a[c] = c + 1
	for i in range(1, len(ccl)):
		a[ccl[i]] = c + 1
	print(*a)
else:
	print(len(ccl) + len(par) - 1)
	c = par[0]
	for i in range(1, len(par)):
		a[par[i]] = c + 1
	for i in range(len(ccl)):
		a[ccl[i]] = c + 1
	print(*a)


tree_size = int(input())
parents = [int(x) - 1 for x in input().split(' ')]
num_changes = 0
root = tree_size
for (node, parent) in enumerate(parents):
	if parent == node:
		root = node
		break
visited = set()
finished = set()
visited.add(root)
finished.add(root)
stack = []
fringe = []
for node in range(len(parents)):
	if node not in visited:
		fringe.append(node)
		while fringe:
			cur = fringe.pop()
			visited.add(cur)
			stack.append(cur)
			if parents[cur] not in finished:
				if parents[cur] in visited:
					parents[cur] = root
					num_changes += 1
				else:
					fringe.append(parents[cur])
		while stack:
			finished.add(stack.pop())
if root == tree_size:
	new_root = None
	for (node, parent) in enumerate(parents):
		if parent == root:
			if new_root is None:
				new_root = node
			parents[node] = new_root
for i in range(len(parents)):
	parents[i] += 1
print(num_changes)
print(*parents)


root = -1

def find(i, time):
	parent[i] = time
	while not parent[aa[i]]:
		i = aa[i]
		parent[i] = time
	if parent[aa[i]] == time:
		global root
		if root == -1:
			root = i
		if aa[i] != root:
			aa[i] = root
			global ans
			ans += 1
n = int(input())
aa = [0] + [int(i) for i in input().split()]
parent = [0] * (n + 1)
ans = 0
time = 0
for i in range(1, n + 1):
	if aa[i] == i:
		root = i
		break
for i in range(1, n + 1):
	if not parent[i]:
		time += 1
		find(i, time)
print(ans)
print(*aa[1:])


from collections import defaultdict
from sys import stdin, setrecursionlimit
setrecursionlimit(10 ** 6)
import threading

def f(a):
	n = len(a)
	a = list(map(lambda s: s - 1, a))
	root = None
	for i in range(len(a)):
		if a[i] == i:
			root = i
	vis = [0] * n
	traitors = []
	for i in range(0, n):
		cycle = -1
		cur = i
		move = set()
		while vis[cur] == 0:
			vis[cur] = 1
			move.add(cur)
			if a[cur] in move:
				cycle = cur
			cur = a[cur]
		if cycle != -1:
			traitors.append(cycle)
	ans = len(traitors) - 1
	if root == None:
		a[traitors[0]] = traitors[0]
		root = traitors[0]
		ans += 1
	for i in traitors:
		if i != root:
			a[i] = root
	print(ans)
	a = list(map(lambda s: s + 1, a))
	return a
n = input()
a = list(map(int, input().strip().split()))
print(*f(a))


from collections import deque

def Padre(x, padre):
	while x != padre[x]:
		x = padre[x]
	return x

def FixATree():
	n = int(input())
	A = list(map(lambda x: int(x) - 1, input().split()))
	padre = [x for x in range(0, n)]
	ciclosC = 0
	ciclos = deque([])
	root = []
	for i in range(0, n):
		p = Padre(A[i], padre)
		if p == i:
			if not root and i == A[i]:
				root = [i, A[i]]
			else:
				ciclos.append([i, A[i]])
				ciclosC += 1
		else:
			padre[i] = A[i]
	print(str(ciclosC))
	if ciclosC:
		i = 0
		if not root:
			root = ciclos.popleft()
			i = 1
		while ciclos:
			ciclo = ciclos.popleft()
			padre[ciclo[0]] = root[0]
	PC = [x + 1 for x in padre]
	print(*PC, sep=' ')
FixATree()


import sys
input = sys.stdin.readline
n = int(input())
lis = [0, *list(map(int, input().split()))]
v = [0] * (n + 1)
cycles = set()
roots = set()
for i in range(1, n + 1):
	if v[i] == 0:
		node = i
		while v[node] == 0:
			v[node] = 1
			node = lis[node]
		if v[node] == 2:
			continue
		start = node
		ignore = 0
		l = 1
		while lis[node] != start:
			if v[node] == 2:
				ignore = 1
				break
			v[node] = 2
			node = lis[node]
			l += 1
		if ignore:
			continue
		v[node] = 2
		if l == 1:
			roots.add(node)
		else:
			cycles.add(node)
ans = 0
if roots:
	base = roots.pop()
	for i in roots:
		lis[i] = base
		ans += 1
	for i in cycles:
		lis[i] = base
		ans += 1
elif cycles:
	base = cycles.pop()
	cycles.add(base)
	for i in roots:
		lis[i] = base
		ans += 1
	for i in cycles:
		lis[i] = base
		ans += 1
print(ans)
print(*lis[1:])


from collections import deque

def Padre(x, padre):
	while x != padre[x]:
		x = padre[x]
	return x

def DFS(x, color, padre, ciclos, adyacentes, raiz):
	color[x] = 1
	for y in adyacentes[x]:
		if color[y] == 0:
			DFS(y, color, padre, ciclos, adyacentes, raiz)
			padre[y] = x
		elif color[y] == 2:
			padre[y] = x
		elif y == x and (not raiz):
			raiz = x
		else:
			ciclos.append([x, y])
	color[x] = 2

def Solucion():
	n = int(input())
	A = list(map(lambda x: int(x) - 1, input().split()))
	padre = [x for x in range(0, n)]
	ciclosC = 0
	ciclos = deque([])
	root = []
	for i in range(0, n):
		p = Padre(A[i], padre)
		if p == i:
			if not root and i == A[i]:
				root = [i, A[i]]
			else:
				ciclos.append([i, A[i]])
				ciclosC += 1
		else:
			padre[i] = A[i]
	print(str(ciclosC))
	if ciclosC:
		i = 0
		if not root:
			root = ciclos.popleft()
			i = 1
		while ciclos:
			ciclo = ciclos.popleft()
			padre[ciclo[0]] = root[0]
	PC = [x + 1 for x in padre]
	print(*PC, sep=' ')
Solucion()


n = int(input())
arr = list(map(int, input().split(' ')))
root = -1
for (i, a) in enumerate(arr):
	if i == a - 1:
		root = i
		break
v = [False] * len(arr)
if root > -1:
	v[root] = True
ans = 0
for (i, a) in enumerate(arr):
	if v[i]:
		continue
	v[i] = True
	l = [i]
	a -= 1
	while not v[a]:
		l.append(a)
		v[a] = True
		a = arr[a] - 1
	if a in l:
		if root == -1:
			arr[a] = a + 1
			root = a
			ans += 1
		else:
			arr[a] = root + 1
			ans += 1
print(ans)
print(' '.join(map(str, arr)))