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