Ранг
Задана матрица, состоящая только из 0 и 1. В каждой колонке матрицы находится в точности две 1. Вычислить ранг матрицы.
Рангом матрицы называется наибольшее число k такое, что существует множество k линейно независимых строк. Множество {v[1], ..., v[k]} называется линейно независимым, если для любых действительных чисел a[1], ..., a[k] таких что a[1]^2 + ... + a[k]^2 ≠ 0 имеет место неравенство a[1] * v[1] + ... + a[k] * v[k] ≠ 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 * 10^5, 1 ≤ m ≤ 2 * 10^5): количество строк и колонок в матрице. Каждая из следующих 2m строк содержит два числа r и c (1 ≤ r ≤ n, 1 ≤ c ≤ m), задающих позиции 1 в матрице. Здесь r - номер строки, c - номер колонки. Все ячейки, не перечисленные в списке, равны нулю. Гарантируется, что все пары (r, c) различны, каждая колонка матрицы содержит в точности две 1.
Выходные данные
Вывести одно число: ранг матрицы.
