Pairs

Description:

Input:

The first line contains an integer n (2 ≤ n ≤ 10⁵), n is the number of students per class. Next, n lines contain information about the students, one per line. Each line contains two integers f_i, s_i (1 ≤ f_i ≤ n, f_i ≠ i, 1 ≤ s_i ≤ 2), where f_i is the number of i-th student's best friend and s_i denotes the i-th pupil's sex (s_i = 1 for a boy and s_i = 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 a_i, b_i (1 ≤ a_i, b_i ≤ 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.

Sample Input:

5
5 2
3 2
5 1
2 1
4 2

Sample Output:

2 2
5 3
4 2

Sample Input:

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

Sample Output:

3 1
4 2
5 1
3 6

Sample Input:

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

Sample 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.