Scheme

E.java

import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Problem {
	public static int n;
	public static List<Integer> g[], rg[], starts[], ends[], cycles[];
	
	public static boolean visited[];
	public static int groups[];
	public static int group = 0;
	public static class Pair{
		int a,b;
		Pair(int a, int b){
			this.a = a;
			this.b = b;
		}
	}
	public static void main(String[] arg) {
		FastScanner scan = new FastScanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		n = scan.nextInt();
		
		g = new ArrayList[n+1];
		rg = new ArrayList[n+1];
		starts = new ArrayList[n+1];
		ends = new ArrayList[n+1];
		cycles = new ArrayList[n+1];
		
		for(int i = 0; i <= n; i++){
			g[i] = new ArrayList<Integer>();
			rg[i] = new ArrayList<Integer>();
			starts[i] = new ArrayList<Integer>();
			ends[i] = new ArrayList<Integer>();
			cycles[i] = new ArrayList<Integer>();
		}
		
		for(int i = 1; i <= n; i++){
			int t = scan.nextInt();
			g[i].add(t);
			rg[t].add(i);
		}
		groups = new int[n+1];
		visited = new boolean[n+1];
		group = 0;
		for(int i = 1; i <= n; i++){
			if(!visited[i]){
				dfs(i);
				group++;
			}
		}
		if(group == 1 && starts[0].size() == 0 && cycles[0].size() > 0){
			out.println(0);
			out.close();
			return;
		}
		
		int i = 0;
		List<Integer> bstarts = null;
		List<Integer> bends = null;
		List<Integer> bcycles = null;
		List<Pair> rets = new ArrayList<Pair>();
		boolean finished = false;
		while(i < n){
			if(starts[i].size() > 0 || cycles[i].size() > 0){
				if(bstarts == null){
					bstarts = starts[i];
					bends = ends[i];
					bcycles = cycles[i];
				} else {
					if(starts[i].size() == 0){
						if(bends.size() == 0){
							for(Integer start : cycles[i]){
								rets.add(new Pair(bcycles.get(0), start));
							}
						} else {
							for(Integer start : cycles[i]){
								rets.add(new Pair(bends.get(0), start));
							}
						}
					} else {
						if(bends.size() == 0){
							for(Integer start : starts[i]){
								rets.add(new Pair(bcycles.get(0), start));
							}
						} else {
							for(Integer start : starts[i]){
								rets.add(new Pair(bends.get(0), start));
							}
						}
					}
					bstarts = starts[i];
					bends = ends[i];
					bcycles = cycles[i];
				}
			}
			i++;

			if(finished) break;
			
			if(i == n && finished == false){
				i = 0;
				finished = true;
			}
		}
		out.println(rets.size());
		for(Pair p : rets){
			out.println(p.a + " " + p.b);
		}
		out.close();
	}

	public static void dfs(int node){
		
		if(visited[node]){
			if(cycles[groups[node]].size() == 0) cycles[groups[node]].add(node);
			return;
		}
		
		visited[node] = true;
		groups[node] = group;
		List<Integer> nexts = g[node];
		for(Integer next : nexts){
			dfs(next);
		}
		
		if(nexts.size() == 0){
			ends[groups[node]].add(node);
		} else {
			if(groups[node] != groups[nexts.get(0)]){
				groups[node] = groups[nexts.get(0)];
			}
		}
		if(rg[node].size() == 0){
			starts[groups[node]].add(node);
		}
	}
	
	static class FastScanner {
		BufferedReader br;
		StringTokenizer st;

		FastScanner(InputStream is) {
			try {
				br = new BufferedReader(new InputStreamReader(is));
			} catch (Exception e) {
				e.printStackTrace();
			}
		}

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

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

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

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