Problem: 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 p1, p2, ..., pn, where pi 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 p1, p2, ..., pn, one is able to restore a tree:

  1. There must be exactly one index r that pr = r. A vertex r is a root of the tree. 
  2. For all other n - 1 vertices i, there is an edge between vertex i and vertex pi. 



A sequence p1, p2, ..., pn 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 a1, a2, ..., an, 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 a1, a2, ..., an (1 ≤ ai ≤ 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 (a1, a2, ..., an) 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 p4 = 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.

Solution (in JAVA):

Solution:
/*
 * 
 * CREATED BY : NAITIK V
 * 
 *     JAI HIND
 * 
 */

import java.util.*;
import java.io.*;
public class A		
{ 
			 static FastReader sc=new FastReader(); 
			 static long dp[][];
			 static int mod=1000000007;
		     public static void main(String[] args)
		    {
			  PrintWriter out=new PrintWriter(System.out);
			  StringBuffer sb=new StringBuffer("");
			 
		  int ttt=1;
		 //  ttt =i();
		    outer :while (ttt-- > 0) 
			{
		    	int n=i();
		    	int B[]=input(n);
		    	int C[]=new int[n];
		    	for(int i=0;i<n;i++)
		    		C[i]=B[i];
		    	ArrayList<Integer> A[]=new ArrayList[n+1];
	        	for(int i=0;i<A.length;i++) {
	        		A[i]=new ArrayList<Integer>();
	        	}
	        	ArrayList<ArrayList<Integer>> l=new ArrayList<>();
	        	//HashMap<Integer,Integer> set=new HashMap<>();
	        	ArrayList<Integer> cou=new ArrayList<Integer>();
	        	for(int i=0;i<n;i++) {
	        		A[i+1].add(B[i]);
	        		if(B[i]!=(i+1))
	        		A[B[i]].add(i+1);
	        		
	        	}
	        	boolean v[]=new boolean[n+1];
	        	for(int i=1;i<=n;i++) {
	        		cou.clear();
	        		if(v[i])
	        			continue;
	        		dfs(A, i, v, cou);
	        		ArrayList<Integer> ll=new ArrayList<Integer>();
	        		for(int k : cou) {
	        			ll.add(k);
	        		}
	        		l.add(ll);
	        	}
//	        	for(int i : l.get(0).keySet()) {
//	        		System.out.print(i+" ");
//	        	}
//	        	System.out.println();
	        	int par=-1;
	        	for(int i=0;i<n;i++) {
	        		if(B[i]==(i+1)) {
	        			par=B[i];
	        			break;
	        		}
	        	}
	        	Arrays.fill(v, false);
	        	boolean u[]=new boolean[n+1];
	        	if(par==-1) {
	        		ArrayList<Integer> m=l.get(0);
	        		for(int key : m) {
	        			int a=B[key-1];
	        			int b=B[a-1];
	        			if(key==b) {
	        				par=a;
	        				B[a-1]=a;
	        				break;
	        			}
	        		}
	        		if(par==-1) {
	        			int child=cycle(A, m.get(0), v, -1);
//		        		int pr=cyclepar(A, m.firstKey(), u, -1);
//		        		System.out.println(child+" "+pr);
	        			par=child;
	        			B[child-1]=child;
		        		
//		        		for(int k : m.keySet()) {
//		        			int a=B[k-1];
//		        			int b=B[a-1];
//		        			if((a==child && pr==b) || (a==pr && b==child)) {
//		        				par=k;
//		        				B[k-1]=par;
//		        				break;
//		        			}
//		        		}
		        		
	        		}
	        		out : for(int i=1;i<l.size();i++) {
		        		 m=l.get(i);
		        		
		        		for(int key : m) {
		        			int a=B[key-1];
		        			int b=B[a-1];
		        			if(key==b) {
		        				B[a-1]=par;
		        				continue out;
		        			}
		        		}
		        		
		        		int child=cycle(A, m.get(0), v, -1);
//		        		int pr=cyclepar(A, m.firstKey(), u, -1);
//		        		for(int k : m.keySet()) {
//		        			int a=B[k-1];
//		        			int b=B[a-1];
//		        			if((a==child && pr==b) || (a==pr && b==child)) {
//		        				B[k-1]=par;
//		        				continue out;
//		        			}
//		        		}
		        		B[child-1]=par;
		        		
		        	}
	        	}
	        	else {
	        	out : for(int i=0;i<l.size();i++) {
	        		ArrayList<Integer> m=l.get(i);
	        		
	        		for(int key : m) {
	        			int a=B[key-1];
	        			int b=B[a-1];
	        			if(key==b) {
	        				B[a-1]=par;
	        				continue out;
	        			}
	        		}
	        		
	        		int child=cycle(A, m.get(0), v, -1);
//	        		int pr=cyclepar(A, m.firstKey(), u, -1);
//	        		for(int k : m.keySet()) {
//	        			int a=B[k-1];
//	        			int b=B[a-1];
//	        			if((a==child && pr==b) || (a==pr && b==child)) {
//	        				B[k-1]=par;
//	        				continue out;
//	        			}
//	        		}
	        		B[child-1]=par;
	        		
	        	}
	        	}
	        	int ans=0;
	        	for(int i=0;i<n;i++) {
	        		if(B[i]!=C[i]) {
	        			ans++;
	        		}
	        	}
	        	System.out.println(ans);
	        	for(int i : B) {
	        		out.print(i+" ");
	        	}
		    	
			}
		   out.close();
		  // System.out.println(sb.toString());
		   
		   
		   //CHECK FOR N=1                    //CHECK FOR M=0
		    //CHECK FOR N=1                    //CHECK FOR M=0
		   	//CHECK FOR N=1
		   	//CHECK FOR N=1
		   	//CHECK FOR N=1
    }
			  
		     
		    

			  
			  private static void dfs(ArrayList<Integer>[] A, int i, boolean[] v,ArrayList<Integer> l) {
				// TODO Auto-generated method stub
				  v[i]=true;
				 l.add(i);
				  for(int child : A[i]) {
					  if(!v[child]) {
						  dfs(A, child, v,l);
					  }
				  }
			}

			  private static int cycle(ArrayList<Integer>[] A, int i, boolean[] v, int par) {
					
					v[i]=true;
					//System.out.println(i);
					for(int child : A[i]) {
						if(!v[child]) {
							int res=cycle(A, child, v, i);
							if(res!=-1)
								return res;
							
						}
						else {
							if(child !=par && par!=-1) {
								return child;
								
							}
						}
					}
					
							return -1;
						}

			  private static int cyclepar(ArrayList<Integer>[] A, int i, boolean[] v, int par) {
					
					v[i]=true;
					for(int child : A[i]) {
						if(!v[child]) {
							int res=cyclepar(A, child, v, i);
							if(res!=-1)
								return res;
							
						}
						else {
							if(child !=par && par!=-1) {
								return i;
							}
						}
					}
					
							return -1;
						}

		     
		     
		     
		     
		     
		     
		     
		     
  static class Pair implements Comparable<Pair>
   {
	   int x;
	   int y;
	  	 Pair(int x,int y){
	  		 this.x=x;
	  		 this.y=y;
	  	 }
	@Override
//	public int compareTo(Pair o) {
//		if(this.x>o.x)
//			return 1;
//		else if(this.x<o.x)
//			return -1;
//		else {
//			if(this.y<o.y)
//				return 1;
//			else if(this.y>o.y)
//				return -1;
//			else
//				return 0;
//		}
//	}
	
	
	public int compareTo(Pair o) {
			if (x > o.x) {
				return 1;
			}
			if (x < o.x) {
				return -1;
			}
			if (y > o.y) {
				return 1;
			}
			if (y < o.y) {
				return -1;
			}
			return 0;
		}
	
 }
static int[] input(int n) {
  	int A[]=new int[n];
  	   for(int i=0;i<n;i++) {
  		   A[i]=sc.nextInt();
  	   }
  	   return A;
     }
  static long[] inputL(int n) {
  	long A[]=new long[n];
  	   for(int i=0;i<n;i++) {
  		   A[i]=sc.nextLong();
  	   }
  	   return A;
     }
  static String[] inputS(int n) {
  	String A[]=new String[n];
  	   for(int i=0;i<n;i++) {
  		   A[i]=sc.next();
  	   }
  	   return A;
     }
  static long sum(int A[]) {
  	long sum=0;
  	for(int i : A) {
  		sum+=i;
  	}
  	return sum;
  }
  static long sum(long A[]) {
  	long sum=0;
  	for(long i : A) {
  		sum+=i;
  	}
  	return sum;
  }

  static void input(int A[],int B[]) {
  	   for(int i=0;i<A.length;i++) {
  		   A[i]=sc.nextInt();
  		   B[i]=sc.nextInt();
  	   }
  }
  static int[][] input(int n,int m){
  	int A[][]=new int[n][m];
  	for(int i=0;i<n;i++) {
  		for(int j=0;j<m;j++) {
  			A[i][j]=i();
  		}
  	}
  	return A;
  }
  static char[][] charinput(int n,int m){
  	char A[][]=new char[n][m];
  	for(int i=0;i<n;i++) {
  		String s=s();
  		for(int j=0;j<m;j++) {
  			A[i][j]=s.charAt(j);
  		}
  	}
  	return A;
  }
  static int max(int A[]) {
  	int max=Integer.MIN_VALUE;
  	for(int i=0;i<A.length;i++) {
  		max=Math.max(max, A[i]);
  	}
  	return max;
  }
  static int min(int A[]) {
  	int min=Integer.MAX_VALUE;
  	for(int i=0;i<A.length;i++) {
  		min=Math.min(min, A[i]);
  	}
  	return min;
  }
  static long max(long A[]) {
  	long max=Long.MIN_VALUE;
  	for(int i=0;i<A.length;i++) {
  		max=Math.max(max, A[i]);
  	}
  	return max;
  }
  static long min(long A[]) {
  	long min=Long.MAX_VALUE;
  	for(int i=0;i<A.length;i++) {
  		min=Math.min(min, A[i]);
  	}
  	return min;
  }
  static long mod(long x) {
  	 int mod=1000000007;
  	  return ((x%mod + mod)%mod);
  }
  static String reverse(String s) {
  	StringBuffer p=new StringBuffer(s);
  	p.reverse();
  	return p.toString();
  }

       static int i() {
      	 return sc.nextInt();
       }
       static String s() {
      	 return sc.next();
       }
       static long l() {
      	 return sc.nextLong();
       }  
       static void sort(int[] A){
          int n = A.length;
          Random rnd = new Random();
          for(int i=0; i<n; ++i){
              int tmp = A[i];
              int randomPos = i + rnd.nextInt(n-i);
              A[i] = A[randomPos];
              A[randomPos] = tmp;
          }
          Arrays.sort(A);
       }
       static void sort(long[] A){
  	        int n = A.length;
  	        Random rnd = new Random();
  	        for(int i=0; i<n; ++i){
  	            long tmp = A[i];
  	            int randomPos = i + rnd.nextInt(n-i);
  	            A[i] = A[randomPos];
  	            A[randomPos] = tmp;
  	        }
  	        Arrays.sort(A);
  	     }
    static String sort(String s) {
   	 Character ch[]=new Character[s.length()];
   	 for(int i=0;i<s.length();i++) {
   		 ch[i]=s.charAt(i);
   	 }
   	 Arrays.sort(ch);
   	 StringBuffer st=new StringBuffer("");
 for(int i=0;i<s.length();i++) {
	 st.append(ch[i]);
 }
 return st.toString();
}
static HashMap<Integer,Integer> hash(int A[]){
  HashMap<Integer,Integer> map=new HashMap<Integer, Integer>();
  for(int i : A) {
	  if(map.containsKey(i)) {
		  map.put(i, map.get(i)+1);
	  }
	  else {
		  map.put(i, 1);
	  }
  }
  return map;
}
static HashMap<Long,Integer> hash(long A[]){
	  HashMap<Long,Integer> map=new HashMap<Long, Integer>();
	  for(long i : A) {
		  if(map.containsKey(i)) {
			  map.put(i, map.get(i)+1);
		  }
		  else {
			  map.put(i, 1);
		  }
	  }
	  return map;
	}
static TreeMap<Integer,Integer> tree(int A[]){
  TreeMap<Integer,Integer> map=new TreeMap<Integer, Integer>();
  for(int i : A) {
	  if(map.containsKey(i)) {
		  map.put(i, map.get(i)+1);
	  }
	  else {
		  map.put(i, 1);
	  }
  }
  return map;
}
static TreeMap<Long,Integer> tree(long A[]){
	  TreeMap<Long,Integer> map=new TreeMap<Long, Integer>();
	  for(long i : A) {
		  if(map.containsKey(i)) {
			  map.put(i, map.get(i)+1);
		  }
		  else {
			  map.put(i, 1);
		  }
	  }
	  return map;
	}
static void primefact(int n) {
	  for(int i=2;i*i<=n;i++) {
		  if(n%i==0) {
			  int cnt=0;
			  while(n%i==0) {
				  cnt++;
				  n/=i;
			  }
			  System.out.println(i+"^"+cnt);
			  
		  }
	  }
	  if(n>1) {
		  System.out.println(n+"^ 1");
	  }
}
   static boolean prime(int n) 
    { 
        if (n <= 1) 
            return false; 
        if (n <= 3) 
            return true; 
        if (n % 2 == 0 || n % 3 == 0) 
            return false; 
        double sq=Math.sqrt(n);
  
        for (int i = 5; i <= sq; i = i + 6) 
            if (n % i == 0 || n % (i + 2) == 0) 
                return false; 
        return true; 
    } 
   static boolean prime(long n) 
    { 
        if (n <= 1) 
            return false; 
        if (n <= 3) 
            return true; 
        if (n % 2 == 0 || n % 3 == 0) 
            return false; 
        double sq=Math.sqrt(n);
  
        for (int i = 5; i <= sq; i = i + 6) 
            if (n % i == 0 || n % (i + 2) == 0) 
                return false; 
        return true; 
    } 
   static long power(long x, long y, long p)
   {

       long res = 1;
       x = x % p;

       while (y > 0) {

           if (y % 2 == 1)
               res = (res * x) % p;

           y = y >> 1; 
           x = (x * x) % p;
       }

       return res;
   }

   static long modInverse(long n, long p)
   {
       return power(n, p - 2, p);
   }
   static int gcd(int a, int b) 
   { 
       if (a == 0) 
           return b; 
       return gcd(b % a, a); 
   } 
   static long gcd(long a, long b) 
   { 
       if (a == 0) 
           return b; 
       return gcd(b % a, a); 
   } 
  
      
  static class FastReader 
  { 
      BufferedReader br; 
      StringTokenizer st; 

      public FastReader() 
      { 
          br = new BufferedReader(new
                   InputStreamReader(System.in)); 
      } 

      String next() 
      { 
          while (st == null || !st.hasMoreElements()) 
          { 
              try
              { 
                  st = new StringTokenizer(br.readLine()); 
              } 
              catch (IOException  e) 
              { 
                  e.printStackTrace(); 
              } 
          } 
          return st.nextToken(); 
      } 

      int nextInt() 
      { 
          return Integer.parseInt(next()); 
      } 

      long nextLong() 
      { 
          return Long.parseLong(next()); 
      } 

      double nextDouble() 
      { 
          return Double.parseDouble(next()); 
      } 

      String nextLine() 
      { 
          String str = ""; 
              try
              { 
                  str = br.readLine(); 
              } 
              catch (IOException e) 
              { 
                  e.printStackTrace(); 
              } 
              return str; 
          } 
      } 
  }