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