1801: Дороги Потоколяндії
Переглянути як PDF
Надіслати розвʼязок
Бали:
22,00 (частково)
Ліміт часу:
1.0s
Ліміт памʼяті:
250M
Автор:
Тип задачі
Дозволені мови
Assembly, Awk, Brain****, C, C++, Java, mono C#, Pascal, Perl, Python, Sed, Text, vb
У Потоколяндії ~n~ міст та ~n~ двосторонніх доріг. ~i~-а дорога з'єднує міста ~i~ та ~(i+i)~ (якщо ~i+i>n~, то ~i+i-n~).
Наприклад, якщо ~n=5~, то будуть дороги ~(1, 2)~, ~(2, 4)~, ~(3, 1)~, ~(4, 3)~, ~(5, 5)~.
З'ясуйте, чи з кожного міста можна потрапити у будь-яке інше місто, рухаючись дорогами. Якщо ні, то знайдіть пару міст, які не з'єднані.
Формат вхідних даних
Перший рядок містить одне ціле число ~n~ (~1 \leq n \leq 10^6~).
Формат вихідних даних
Виведіть ~YES~, якщо з кожного міста можна потрапити у будь-яке інше місто.
Інакше, у першому рядку виведіть ~NO~. У другому рядку виведіть будь-які два міста ~a~ та ~b~ (~1 \leq a, b \leq n~; ~a \neq b~) такі, що з міста ~a~ неможливо потрапити у ~b~, рухаючись дорогами.
Приклад вхідних даних
5
Приклад вихідних даних
NO
1 5
Приклад вхідних даних
4
Приклад вихідних даних
YES
Приклад вхідних даних
7
Приклад вихідних даних
NO
1 7
Приклад вхідних даних
8
Приклад вихідних даних
YES
Коментарі
Моя програма видає при n=7 відповідь NO 1 3 Але проходить лише така відповідь NO 1 7 Чому так, адже можна вивести будь-яку пару вершин? Для даного тесту зв'язані вершини 1, 2 , 4 та 3, 5, 6. 7 ізольована В чому проблема?