eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Большие перемены

Большие перемены

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

В Тридевятом царстве n городов. Король хочет соединить города n - 1 двусторонней авиалинией так, чтобы:

  • Каждая авиалиния соединяла два различных города.

  • Из каждого города можно было добраться в любой другой напрямую или с пересадками.

Назовем доступностью города количество городов, с которыми он напрямую соединен авиалиниями. Король также требует, чтобы максимальное значение доступности среди всех городов королевства было как можно большим.

Сколько существует различных способов соединить города требуемым образом?

Входные данные

Одно целое число n (2n10^9) - количество городов.

Выходные данные

Выведите одно целое число - ответ на задачу.

Пример

Входные данные #1
3
Выходные данные #1
3

Примечание

Максимальное возможное значение доступности для трех городов равно 2. Возможны три различных варианта соединения, при котором оно достигается: (1,2) и (2,3), (1,3) и (2,3), (1,2) и (1,3).

Источник 2019 ACM NEERC, Квалификация, Октябрь 6, Задача B