Ранг
Ранг
Задана матрица, состоящая только из 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.
Выходные данные
Вывести одно число: ранг матрицы.
3 3 1 1 2 1 2 2 3 2 1 3 3 3
3