eolymp
bolt
Try our new interface for solving problems

Ранг

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

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

Рангом матрицы называется наибольшее число k такое, что существует множество k линейно независимых строк. Множество {v[1], ..., v[k]} называется линейно независимым, если для любых действительных чисел a[1], ..., a[k] таких что a[1]^2 + ... + a[k]^20 имеет место неравенство 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).

Giriş verilənləri

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

Çıxış verilənləri

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

prb6462.gif

Nümunə

Giriş verilənləri #1
3 3
1 1
2 1
2 2
3 2
1 3
3 3
Çıxış verilənləri #1
3
Mənbə 2013 Петрозаводск, MIPT contest, Август 25, Задача F