Рождество! Польшар и его друзья будут дарить друг другу подарки. Всего шаров n. Каждый шар должен подарить подарок ровно одному другому шару в соответствии с некоторой перестановкой p, pi ≠ i для всех i.
К сожалению, шары забывчивы. Мы знаем, что ровно k шаров забудут принести свои подарки. Шар номер i получит подарок, если будут выполнены следующие два условия:
- Шар номер i должен принести свой подарок.
- Шар x такой, что px = i, должен принести свой подарок.
Какое минимально и максимально возможное число шаров, которые не получат свой подарок, если ровно k шаров забудут принести свой подарок?
Выходные данные
Выведите два числа — минимально и максимально возможное число шаров, которые не получат подарков, соответственно.
Примечание
В первом примере, если первый и третий шары забудут принести подарок, то они же и будут единственными, кто не получит подарка. Поэтому минимальный ответ равен 2. Однако, если первый и второй шары забудут, то только пятый шар получит подарок. Поэтому максимальный ответ равен 4.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 2
3 4 1 5 2
|
2 4
|
|
2
|
10 1
2 3 4 5 6 7 8 9 10 1
|
2 2
|