| Яндекс.Алгоритм 2011: Квалификация 1 |
|---|
| Закончено |
В классе у Поликарпа учится n человек (включая его самого). Недавно все ученики класса писали сочинение «Мой лучший друг». Сочинение каждого ученика было посвящено одному из учеников класса — лучшему другу. Заметим, что вовсе не обязательно у ученика b лучшим другом является ученик a, если у a лучший друг — b.
А сейчас учительница ведет весь класс в музей истории спортивного программирования. Учеников ждут захватывающие истории о легендарных героях: tourist, Petr, tomek, SnapDragon — вот о ком пойдет речь!
Учительница решила разбить учеников на пары так, чтобы каждая пара состояла из ученика и его лучшего друга. Возможно, ей не удастся разбить всех учеников на пары, не беда — она хочет выделить наибольшее количество таких пар. Если существует более одного варианта сделать это, она хочет выделить пары так, чтобы пар мальчик-девочка было как можно больше. Конечно, каждый ученик должен входить не более чем в одну пару.
Первая строка содержит целое число n (2 ≤ n ≤ 105), n — количество учеников в классе. Далее в n строках содержится информация об учениках, по одному в строке. Каждая строка содержит два целых числа fi, si (1 ≤ fi ≤ n, fi ≠ i, 1 ≤ si ≤ 2), где fi обозначает номер лучшего друга i-го ученика, а si обозначает пол i-го ученика (если мальчик, то si = 1, а если девочка, то si = 2).
В первую строку выведите два числа t, e, где t — максимальное количество образованных пар, а e — максимальное количество среди них пар вида мальчик-девочка. Далее выведите t строк, каждая из строк должна содержать пару ai, bi (1 ≤ ai, bi ≤ n) — номера учеников в i-ой паре. Пары выводите в любом порядке. Числа в парах выводите в любом порядке. Если существует несколько решений, выведите любое.
5
5 2
3 2
5 1
2 1
4 2
2 2
5 3
4 2
6
5 2
3 2
5 1
2 1
4 2
3 1
3 1
4 2
5 1
3 6
8
2 2
3 2
5 1
3 1
6 1
5 1
8 2
7 1
4 1
5 6
3 4
2 1
7 8
Рисунок ниже соответствует первому примеру. На нем ромбы обозначают мальчиков, а квадраты — девочек. Стрелки ведут от ученика к его лучшему другу, жирные (не пунктирные) обозначают пары из ответа.
