Problem: To learn as soon as possible the latest news about their favourite fundamentally new operating system, BolgenOS community from Nizhni Tagil decided to develop a scheme. According to this scheme a community member, who is the first to learn the news, calls some other member, the latter, in his turn, calls some third member, and so on; i.e. a person with index i got a person with index fi, to whom he has to call, if he learns the news. With time BolgenOS community members understood that their scheme doesn't work sometimes — there were cases when some members didn't learn the news at all. Now they want to supplement the scheme: they add into the scheme some instructions of type (xi, yi), which mean that person xi has to call person yi as well. What is the minimum amount of instructions that they need to add so, that at the end everyone learns the news, no matter who is the first to learn it?

Input

The first input line contains number n (2 ≤ n ≤ 105) — amount of BolgenOS community members. The second line contains n space-separated integer numbers fi (1 ≤ fi ≤ n, i ≠ fi) — index of a person, to whom calls a person with index i.

Output

In the first line output one number — the minimum amount of instructions to add. Then output one of the possible variants to add these instructions into the scheme, one instruction in each line. If the solution is not unique, output any.

Examples

Input

3
3 3 2


Output

1
3 1


Input

7
2 3 1 3 4 4 1


Output

3
2 5
2 6
3 7

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;

public class Main implements Runnable {
	class MyList {
		int[] array = new int[10];
		int at;

		public void add(int val) {
			if (at == array.length) {
				int[] next = new int[2 * array.length];
				System.arraycopy(array, 0, next, 0, array.length);
				array = next;
			}
			array[at++] = val;
		}

		public int get(int index) {
			return array[index];
		}

		public int size() {
			return at;
		}
	}

	public void solution() throws IOException {
		int n = in.nextInt();
		MyList[] v = new MyList[n];
		MyList[] rv = new MyList[n];
		for (int i = 0; i < n; ++i) {
			v[i] = new MyList();
			rv[i] = new MyList();
		}
		for (int i = 0; i < n; ++i) {
			int x = i;
			int y = in.nextInt() - 1;
			v[x].add(y);
			rv[y].add(x);
		}
		MyList order = new MyList();
		boolean[] used = new boolean[n];
		for (int i = 0; i < n; ++i) {
			if (!used[i]) {
				dfs(i, v, used, order);
			}
		}
		Arrays.fill(used, false);
		int[] comp = new int[n];
		Arrays.fill(comp, -1);
		for (int i = 0; i < n; ++i) {
			int x = order.get(n - i - 1);
			if (comp[x] == -1) {
				dfs2(x, rv, comp, x);
			}
		}
		boolean[] start = new boolean[n];
		for (int x : comp) {
			if (x != -1) {
				start[x] = true;
			}
		}
		MyList[] nv = new MyList[n];
		for (int i = 0; i < n; ++i) {
			nv[i] = new MyList();
		}
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < v[i].size(); ++j) {
				int x = v[i].get(j);
				if (comp[i] != comp[x]) {
					start[comp[x]] = false;
					nv[comp[i]].add(comp[x]);
				}
			}
		}
		class Comp {
			int start;
			MyList end;

			public Comp(int start, MyList end) {
				this.start = start;
				this.end = end;
			}
		}
		List<Comp> comps = new ArrayList<Comp>();
		Arrays.fill(used, false);
		for (int i = 0; i < n; ++i) {
			if (start[i]) {
				MyList cur = new MyList();
				dfs3(i, nv, used, cur);
				comps.add(new Comp(i, cur));
			}
		}
		class Pair {
			int x;
			int y;

			public Pair(int x, int y) {
				this.x = x;
				this.y = y;
			}

			@Override
			public String toString() {
				return x + " " + y;
			}
		}
		List<Pair> ans = new ArrayList<Pair>();
		for (int i = 0; i < comps.size(); ++i) {
			for (int j = 0; j < comps.get(i).end.size(); ++j) {
				int x = comps.get(i).end.get(j);
				int a = x + 1;
				int b = comps.get((i + 1) % comps.size()).start + 1;
				if (a != b) {
					ans.add(new Pair(a, b));
				}
			}
		}
		out.println(ans.size());
		for (Pair p : ans) {
			out.println(p);
		}
	}

	private void dfs3(int at, MyList[] nv, boolean[] used, MyList cur) {
		if (used[at]) {
			return;
		}
		if (nv[at].size() == 0) {
			cur.add(at);
		} else {
			for (int i = 0; i < nv[at].size(); ++i) {
				int next = nv[at].get(i);
				dfs3(next, nv, used, cur);
			}
		}
	}

	private void dfs2(int at, MyList[] rv, int[] comp, int p) {
		if (comp[at] != -1) {
			return;
		}
		comp[at] = p;
		for (int i = 0; i < rv[at].size(); ++i) {
			int next = rv[at].get(i);
			dfs2(next, rv, comp, p);
		}
	}

	private void dfs(int at, MyList[] v, boolean[] used, MyList order) {
		if (used[at]) {
			return;
		}
		used[at] = true;
		for (int i = 0; i < v[at].size(); ++i) {
			int next = v[at].get(i);
			dfs(next, v, used, order);
		}
		order.add(at);
	}

	public void run() {
		try {
			solution();
			in.reader.close();
			out.close();
		} catch (Throwable e) {
			e.printStackTrace();
			System.exit(1);
		}
	}

	private class Scanner {
		private BufferedReader reader;
		private StringTokenizer tokenizer;

		public Scanner(Reader reader) {
			this.reader = new BufferedReader(reader);
			this.tokenizer = new StringTokenizer("");
		}

		public boolean hasNext() throws IOException {
			while (!tokenizer.hasMoreTokens()) {
				String next = reader.readLine();
				if (next == null) {
					return false;
				}
				tokenizer = new StringTokenizer(next);
			}
			return true;
		}

		public String next() throws IOException {
			hasNext();
			return tokenizer.nextToken();
		}

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

		public String nextLine() throws IOException {
			tokenizer = new StringTokenizer("");
			return reader.readLine();
		}
	}

	public static void main(String[] args) throws IOException {
		new Thread(null, new Main(), "", 1 << 28).start();
	}
	PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
	Scanner in = new Scanner(new InputStreamReader(System.in));
}