B. Задачи для раунда
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для очередного раунда Codeforces были подготовлены n задач. Задачи упорядочены по возрастанию сложности, при этом сложности всех задач различны. Дополнительно про некоторые m пар задач известно, что они похожи. Авторы раунда решили поделить задачи между двумя дивизионами согласно следующим правилам:

  • В каждом дивизионе будет предложена хотя бы одна задача.
  • Каждая задача будет использована ровно в одном дивизионе (да, это необычное требование для Codeforces).
  • Любая задача, используемая в первом дивизионе, сложнее любой задачи, используемой во втором дивизионе.
  • Если какие-то две задачи похожи, то они обязательно используются в разных дивизионах.

Посчитайте количество способов разбить задачи на два дивизиона, так чтобы выполнялись все правила. Два способа считаются различными, если существует задача, которая в разных способах будет использована в разных дивизионах.

Обратите внимание, что отношение похожести двух задач не является транзитивным, то есть если задача i похожа на задачу j, а задача j похожа на задачу k, то это не означает, что i похожа на k.

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

В первой строке входных данных записаны два числа n и m (2 ≤ n ≤ 100 000, 0 ≤ m ≤ 100 000) — количество подготовленных задач и пар похожих задач соответственно.

В каждой из последующих m строк записана пара похожих задач ui, vi (1 ≤ ui, vi ≤ n, ui ≠ vi). Гарантируется, что никакая пара задач не встречается во входных данных дважды.

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

Выведите единственное целое число — количество способов разбить задачи на два дивизиона.

Примеры
Входные данные
5 2
1 4
5 2
Выходные данные
2
Входные данные
3 3
1 2
2 3
1 3
Выходные данные
0
Входные данные
3 2
3 1
3 2
Выходные данные
1
Примечание

В первом примере задачи 1 и 2 обязательно будут использованы во втором дивизионе, а задачи 4 и 5 — в первом. Задача 3 может быть использована как в первом, так и во втором дивизионе.

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

Третий пример иллюстрирует, что отношение похожести не является транзитивным. Задача 3 похожа на задачу 1 и на задачу 2, но при этом 1 не похожа на 2, и они могут быть использованы для одного дивизиона.