Problem: There are n students in Polycarp's class (including himself). A few days ago all students wrote an essay "My best friend". Each student's essay was dedicated to one of the students of class, to his/her best friend. Note that student b's best friend is not necessarily student a, if a's best friend is b.

And now the teacher leads the whole class to the museum of the history of sports programming. Exciting stories of legendary heroes await the students: tourist, Petr, tomek, SnapDragon — that's who they will hear about!

The teacher decided to divide students into pairs so that each pair consisted of a student and his best friend. She may not be able to split all the students into pairs, it's not a problem — she wants to pick out the maximum number of such pairs. If there is more than one variant of doing so, she wants to pick out the pairs so that there were as much boy-girl pairs as possible. Of course, each student must not be included in more than one pair.

Input

The first line contains an integer n (2 ≤ n ≤ 105), n is the number of students per class. Next, n lines contain information about the students, one per line. Each line contains two integers fi, si (1 ≤ fi ≤ n, fi ≠ i, 1 ≤ si ≤ 2), where fi is the number of i-th student's best friend and si denotes the i-th pupil's sex (si = 1 for a boy and si = 2 for a girl).

Output

Print on the first line two numbers t, e, where t is the maximum number of formed pairs, and e is the maximum number of boy-girl type pairs among them. Then print t lines, each line must contain a pair ai, bi (1 ≤ ai, bi ≤ n), they are numbers of pupils in the i-th pair. Print the pairs in any order. Print the numbers in pairs in any order. If there are several solutions, output any of them.

Examples

Input

5
5 2
3 2
5 1
2 1
4 2


Output

2 2
5 3
4 2


Input

6
5 2
3 2
5 1
2 1
4 2
3 1


Output

3 1
4 2
5 1
3 6


Input

8
2 2
3 2
5 1
3 1
6 1
5 1
8 2
7 1


Output

4 1
5 6
3 4
2 1
7 8

Note

The picture corresponds to the first sample. On the picture rhomb stand for boys, squares stand for girls, arrows lead from a pupil to his/her best friend. Bold non-dashed arrows stand for pairs in the answer. 

<image>

Solution (in JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.OutputStream;
import java.util.Collection;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.io.BufferedOutputStream;
import java.util.StringTokenizer;
import java.io.Writer;
import java.io.BufferedReader;
import java.util.NoSuchElementException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author An Almost Retired Guy
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        TaskE solver = new TaskE();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskE {
        int[] to;
        boolean[] sex;
        boolean[] vis;
        ArrayList<EzIntIntPair> list;
        EzIntArrayList[] children;
        EzIntArrayList cycle;
        SolverDP0[] dp0;
        SolverDP1[] dp1;
        EzIntArrayList inStack;

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            int n = in.nextInt();
            to = new int[n];
            sex = new boolean[n];
            children = new EzIntArrayList[n];
            dp0 = new SolverDP0[n];
            dp1 = new SolverDP1[n];
            for (int i = 0; i < n; i++) children[i] = new EzIntArrayList();
            for (int i = 0; i < n; i++) {
                to[i] = in.nextInt() - 1;
                sex[i] = in.nextInt() == 1;
                children[to[i]].add(i);
            }
            list = new ArrayList<>();
            int x = 0, y = 0;
            vis = new boolean[n];
            inStack = new EzIntArrayList();
            cycle = new EzIntArrayList();
            for (int i = 0; i < n; i++)
                if (!vis[i]) {
                    EzIntIntPair pair = solveForSubgraph(i);
                    x += pair.first;
                    y += pair.second;
                }
            out.println(x + " " + y);
            for (EzIntIntPair pair : list) out.println((pair.first + 1) + " " + (pair.second + 1));
        }

        EzIntIntPair solveForSubgraph(int u) {
            dfs(u);
            for (int v : cycle.toArray()) children[to[v]].remove(v);
            for (int v : cycle.toArray()) dfs2(v);
            int[] arr0 = cycle.toArray(), arr1 = cycle.toArray();
            ArrayRotate.rotate(arr1, 0, 1, cycle.size());
            SolverDP S0 = new SolverDP(arr0), S1 = new SolverDP(arr1);
            if (S0.value().compareTo(S1.value()) >= 0) {
                S0.restore();
                return S0.value();
            } else {
                S1.restore();
                return S1.value();
            }
        }

        EzIntIntPair dp0(int u) {
            if (dp0[u] == null) dp0[u] = new SolverDP0(u);
            return dp0[u].value();
        }

        EzIntIntPair dp1(int u) {
            if (dp1[u] == null) dp1[u] = new SolverDP1(u);
            return dp1[u].value();
        }

        void dfs(int u) {
            vis[u] = true;
            inStack.add(u);
            int v = to[u];
            if (!vis[v]) dfs(v);
            else {
                cycle.clear();
                for (int i = inStack.indexOf(v); i < inStack.size(); i++) cycle.add(inStack.get(i));
            }
            inStack.removeLast();
        }

        void dfs2(int u) {
            vis[u] = true;
            for (int v : children[u].toArray()) dfs2(v);
        }

        class SolverDP {
            EzIntIntPair[] dp;
            boolean[] used;
            int[] arr;

            SolverDP(int[] arr) {
                this.arr = arr;
                int n = arr.length;
                dp = new EzIntIntPair[n];
                used = new boolean[n];
                for (int i = 0; i < n; i++) {
                    EzIntIntPair pair = dp1(arr[i]);
                    if (i > 0) {
                        EzIntIntPair aux = dp[i - 1];
                        pair = new EzIntIntPair(pair.first + aux.first, pair.second + aux.second);
                    }
                    dp[i] = pair;
                    if (i > 0) {
                        pair = new EzIntIntPair(1 + dp0(arr[i]).first + dp0(arr[i - 1]).first, (sex[arr[i]] != sex[arr[i - 1]] ? 1 : 0) + dp0(arr[i]).second + dp0(arr[i - 1]).second);
                        if (i > 1) {
                            EzIntIntPair aux = dp[i - 2];
                            pair = new EzIntIntPair(pair.first + aux.first, pair.second + aux.second);
                        }
                        if (pair.compareTo(dp[i]) > 0) {
                            dp[i] = pair;
                            used[i] = true;
                        }
                    }
                }
            }

            EzIntIntPair value() {
                return dp[dp.length - 1];
            }

            void restore() {
                for (int pos = dp.length - 1; pos >= 0; pos--) {
                    if (used[pos]) {
                        list.add(new EzIntIntPair(arr[pos], arr[pos - 1]));
                        dp0[arr[pos--]].restore();
                        dp0[arr[pos]].restore();
                    } else dp1[arr[pos]].restore();
                }
            }

        }

        class SolverDP0 {
            int u;
            EzIntIntPair value;

            SolverDP0(int u) {
                this.u = u;
                int x = 0, y = 0;
                for (int v : children[u].toArray()) {
                    x += dp1(v).first;
                    y += dp1(v).second;
                }
                value = new EzIntIntPair(x, y);
            }

            EzIntIntPair value() {
                return value;
            }

            void restore() {
                for (int v : children[u].toArray()) dp1[v].restore();
            }

        }

        class SolverDP1 {
            int u;
            int f;
            EzIntIntPair value;

            SolverDP1(int u) {
                this.u = u;
                f = -1;
                EzIntIntPair sum = dp0(u), ans = sum;
                for (int v : children[u].toArray()) {
                    EzIntIntPair pair = new EzIntIntPair(1 + sum.first - dp1(v).first + dp0(v).first, (sex[u] != sex[v] ? 1 : 0) + sum.second - dp1(v).second + dp0(v).second);
                    if (pair.compareTo(ans) > 0) {
                        ans = pair;
                        f = v;
                    }
                }
                value = ans;
            }

            EzIntIntPair value() {
                return value;
            }

            void restore() {
                if (f != -1) list.add(new EzIntIntPair(u, f));
                for (int v : children[u].toArray()) {
                    if (v != f) dp1[v].restore();
                    else dp0[v].restore();
                }
            }

        }

    }

    static class OutputWriter extends PrintWriter {
        public OutputWriter(OutputStream outputStream) {
            super(new BufferedOutputStream(outputStream));
        }

        public OutputWriter(Writer writer) {
            super(writer);
        }

        public void close() {
            super.close();
        }

    }

    static class EzIntArrayList implements EzIntList, EzIntStack {
        private static final int DEFAULT_CAPACITY = 10;
        private static final double ENLARGE_SCALE = 2.0;
        private static final int HASHCODE_INITIAL_VALUE = 0x811c9dc5;
        private static final int HASHCODE_MULTIPLIER = 0x01000193;
        private int[] array;
        private int size;

        public EzIntArrayList() {
            this(DEFAULT_CAPACITY);
        }

        public EzIntArrayList(int capacity) {
            if (capacity < 0) {
                throw new IllegalArgumentException("Capacity must be non-negative");
            }
            array = new int[capacity];
            size = 0;
        }

        public EzIntArrayList(EzIntCollection collection) {
            size = collection.size();
            array = new int[size];
            int i = 0;
            for (EzIntIterator iterator = collection.iterator(); iterator.hasNext(); ) {
                array[i++] = iterator.next();
            }
        }

        public EzIntArrayList(int[] srcArray) {
            size = srcArray.length;
            array = new int[size];
            System.arraycopy(srcArray, 0, array, 0, size);
        }

        public EzIntArrayList(Collection<Integer> javaCollection) {
            size = javaCollection.size();
            array = new int[size];
            int i = 0;
            for (int element : javaCollection) {
                array[i++] = element;
            }
        }


        public int size() {
            return size;
        }


        public EzIntIterator iterator() {
            return new EzIntArrayListIterator();
        }


        public int[] toArray() {
            int[] result = new int[size];
            System.arraycopy(array, 0, result, 0, size);
            return result;
        }


        public boolean add(int element) {
            if (size == array.length) {
                enlarge();
            }
            array[size++] = element;
            return true;
        }


        public boolean remove(int element) {
            for (int i = 0; i < size; i++) {
                if (array[i] == element) {
                    //noinspection ManualArrayCopy
                    for (int j = i + 1; j < size; j++) {
                        array[j - 1] = array[j];
                    }
                    size--;
                    return true;
                }
            }
            return false;
        }


        public void clear() {
            size = 0;
        }


        public int get(int index) {
            if (index < 0 || index >= size) {
                throw new IndexOutOfBoundsException("Index " + index + " is out of range, size = " + size);
            }
            return array[index];
        }


        public int removeLast() {
            if (size == 0) {
                throw new NoSuchElementException("Trying to call removeLast() on empty ArrayList");
            }
            return array[--size];
        }


        public int indexOf(int element) {
            for (int i = 0; i < size; i++) {
                if (array[i] == element) {
                    return i;
                }
            }
            return -1;
        }

        private void enlarge() {
            int newSize = Math.max(size + 1, (int) (size * ENLARGE_SCALE));
            int[] newArray = new int[newSize];
            System.arraycopy(array, 0, newArray, 0, size);
            array = newArray;
        }


        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            EzIntArrayList that = (EzIntArrayList) o;

            if (size != that.size) {
                return false;
            }
            for (int i = 0; i < size; i++) {
                if (array[i] != that.array[i]) {
                    return false;
                }
            }
            return true;
        }


        public int hashCode() {
            int hash = HASHCODE_INITIAL_VALUE;
            for (int i = 0; i < size; i++) {
                hash = (hash ^ PrimitiveHashCalculator.getHash(array[i])) * HASHCODE_MULTIPLIER;
            }
            return hash;
        }


        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append('[');
            for (int i = 0; i < size; i++) {
                sb.append(array[i]);
                if (i < size - 1) {
                    sb.append(", ");
                }
            }
            sb.append(']');
            return sb.toString();
        }

        private class EzIntArrayListIterator implements EzIntIterator {
            private int curIndex = 0;


            public boolean hasNext() {
                return curIndex < size;
            }


            public int next() {
                if (curIndex == size) {
                    throw new NoSuchElementException("Iterator doesn't have more elements");
                }
                return array[curIndex++];
            }

        }

    }

    static class InputReader {
        BufferedReader br;
        StringTokenizer st;

        public InputReader(InputStream inputStream) {
            br = new BufferedReader(new InputStreamReader(inputStream));
        }

        public String next() {
            while (st == null || !st.hasMoreElements()) {
                st = new StringTokenizer(nextLine());
            }
            return st.nextToken();
        }

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

        public String nextLine() {
            try {
                return br.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }

    }

    static class EzIntIntPair implements Comparable<EzIntIntPair> {
        private static final int HASHCODE_INITIAL_VALUE = 0x811c9dc5;
        private static final int HASHCODE_MULTIPLIER = 0x01000193;
        public final int first;
        public final int second;

        public EzIntIntPair(int first, int second) {
            this.first = first;
            this.second = second;
        }


        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            EzIntIntPair that = (EzIntIntPair) o;

            return first == that.first && second == that.second;
        }


        public int hashCode() {
            int hash = HASHCODE_INITIAL_VALUE;
            hash = (hash ^ PrimitiveHashCalculator.getHash(first)) * HASHCODE_MULTIPLIER;
            hash = (hash ^ PrimitiveHashCalculator.getHash(second)) * HASHCODE_MULTIPLIER;
            return hash;
        }


        public int compareTo(EzIntIntPair other) {
            int cmpU = Integer.compare(first, other.first);
            return cmpU != 0 ? cmpU : Integer.compare(second, other.second);
        }


        public String toString() {
            return "(" + first + ", " + second + ")";
        }

    }

    static final class PrimitiveHashCalculator {
        private PrimitiveHashCalculator() {
        }

        public static int getHash(int x) {
            return x;
        }

    }

    static interface EzIntList extends EzIntCollection {
        int size();

        EzIntIterator iterator();

        boolean equals(Object object);

        int hashCode();

        String toString();

    }

    static interface EzIntCollection {
        int size();

        EzIntIterator iterator();

        boolean equals(Object object);

        int hashCode();

        String toString();

    }

    static interface EzIntIterator {
        boolean hasNext();

        int next();

    }

    static class ArrayRotate {
        public static void rotate(int[] a, int first, int middle, int last) {
            int next = middle;
            while (first != next) {
                swap(a, first++, next++);
                if (next == last)
                    next = middle;
                else if (first == middle)
                    middle = next;
            }
        }

        static void swap(int[] a, int i, int j) {
            int t = a[j];
            a[j] = a[i];
            a[i] = t;
        }

    }

    static interface EzIntStack extends EzIntCollection {
        int size();

        EzIntIterator iterator();

        boolean equals(Object object);

        int hashCode();

        String toString();

    }
}