Задана матрица, состоящая только из 0 и 1. В каждой колонке матрицы находится в точности две 1. Вычислить ранг матрицы.

Рангом матрицы называется наибольшее число k такое, что существует множество k линейно независимых строк. Множество {v1, ..., vk} называется линейно независимым, если для любых действительных чисел a1, ..., ak таких что a1^2 + ... + ak^2 ≠ 0 имеет место неравенство a1 * v1 + ... + ak * vk ≠ 0.

Для строк используются стандартные правила умножения на скаляр и сложения:

a (u(1), ..., u(m)) = (au(1), ..., au(m)),

(u(1), ..., u(m)) + (v(1), ..., v(m)) = (u(1) + v(1), ..., u(m) + v(m)).

Нулевая строка 0 = (0, ..., 0).

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

Первая строка содержит два числа n и m (2 ≤ n ≤ 2 * 105, 1 ≤ m ≤ 2 * 105): количество строк и колонок в матрице. Каждая из следующих 2m строк содержит два числа r и c (1 ≤ r ≤ n, 1 ≤ c ≤ m), задающих позиции 1 в матрице. Здесь r - номер строки, c - номер колонки. Все ячейки, не перечисленные в списке, равны нулю. Гарантируется, что все пары (r, c) различны, каждая колонка матрицы содержит в точности две 1.

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

Вывести одно число: ранг матрицы.