Задача Задание по дискретной математике ≡

Условие

Паша не ходил на дискретную математику весь семестр, но все-таки на комиссию ему не хотелось и он подошел к преподавателю.

Иван Дискретович конечно не хотел давать ему возможность получить оценку, поэтому дал ему очень большой список формул вида: (x₁ ∨ x₂) ∧ (¬ x₁ ∨ x₃) ∧ (¬ x₂ ∨ ¬ x₃), в скобках может содержаться одна или две переменных. Задача Паши определить, может ли обращаться формула в истину. Он был уверен, что Паша не справится.

Паша обратился к вам, помогите ему не попасть на комиссию.

Формат входных данных

В первой строке натуральное число M. В следующих M строках идут целые числа от 1 до N по модулю.

Например для формулы (x₁ ∨ x₂) ∧ (¬ x₁ ∨ x₃) ∧ (¬ x₂ ∨ ¬ x₃) будет следующий ввод:

Формат выходных данных

Если есть набор переменных, обращающих выражение в истину, то выведите Possible, иначе Impossible.

Ограничения

1 ≤ M ≤ 10⁵
|N| ≤ 10⁵
N ≠ 0

Примеры тестов

3
1 2
-1 3
-2 -3
            

Possible

3
1 2
-1
-2
            

Impossible

Задача Экскурсия по Италии ≡

Условие

После очередной победы на Кубке Поршня Молния Маквин решил отдохнуть. Вместе с Луиджи и Гвидо он отправился в Италию. Города в Италии состоят из узких улочек, есть множество перекрестков, соединенных дорогами. Однако, не все части городка могут быть соединены между собой, так как некоторые районы могут быть изолированы.

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

Ваша задача выяснить, сможет ли Маквин совершить подобный заезд.

Формат входных данных

В первой строке натуральное число N - количество дорог. В следующих N строках идут целые числа a_ij b_ij- номера перекрестков, соединенных дорогой, по два в каждой строке. Граф является простым и не имеет изолированных вершин.

Формат выходных данных

Выведите YES, еcли экскурсия возможна. В противном случае выведите NO.

Ограничения

1 ≤ N ≤ 100000
0 ≤ a_ij b_ij ≤ 50000

Примеры тестов

3
0 1
1 2
2 0
            

YES

4
0 1
1 2
1 3
3 2
            

NO

Задача Мошенничество во благо ≡

Условие

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

Но гадалка не из простых обманщиков, она делает все профессионально. Именно поэтому ей нужна помощь с написанием программы, которая достаточно быстро проверяет число на простоту.

Формат входных данных

На вход подается число N.

Формат выходных данных

Вывести "Простое число" в случае, если оно простое, иначе вывести "Составное число".

Ограничения

1 ≤ N ≤ 10⁴⁶

Примеры тестов

2946901

Простое число

750306010782

Составное число