Для очередного раунда Codeforces были подготовлены n задач. Задачи упорядочены по возрастанию сложности, при этом сложности всех задач различны. Дополнительно про некоторые m пар задач известно, что они похожи. Авторы раунда решили поделить задачи между двумя дивизионами согласно следующим правилам:
- В каждом дивизионе будет предложена хотя бы одна задача.
- Каждая задача будет использована ровно в одном дивизионе (да, это необычное требование для Codeforces).
- Любая задача, используемая в первом дивизионе, сложнее любой задачи, используемой во втором дивизионе.
- Если какие-то две задачи похожи, то они обязательно используются в разных дивизионах.
Посчитайте количество способов разбить задачи на два дивизиона, так чтобы выполнялись все правила. Два способа считаются различными, если существует задача, которая в разных способах будет использована в разных дивизионах.
Обратите внимание, что отношение похожести двух задач не является транзитивным, то есть если задача i похожа на задачу j, а задача j похожа на задачу k, то это не означает, что i похожа на k.
Выходные данные
Выведите единственное целое число — количество способов разбить задачи на два дивизиона.
Примечание
В первом примере задачи 1 и 2 обязательно будут использованы во втором дивизионе, а задачи 4 и 5 — в первом. Задача 3 может быть использована как в первом, так и во втором дивизионе.
Во втором примере все пары задач являются похожими, поэтому не существует способа разбить задачи на два дивизиона, не нарушая никаких правил.
Третий пример иллюстрирует, что отношение похожести не является транзитивным. Задача 3 похожа на задачу 1 и на задачу 2, но при этом 1 не похожа на 2, и они могут быть использованы для одного дивизиона.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 2
1 4
5 2
|
2
|
|
2
|
3 3
1 2
2 3
1 3
|
0
|
|
3
|
3 2
3 1
3 2
|
1
|