Rəng
Verilən matris yalnız 0 və 1-lərdən ibarətdir. Hər sütunda dəqiq iki 1 var. Matrisin rütbəsini hesablayın.
Matrisin rütbəsi ən böyük k sayıdır ki, k xətti müstəqil sətirlər çoxluğu mövcuddur. {v[1], ..., v[k]} çoxluğu xətti müstəqil adlanır, əgər elə a[1], ..., a[k] həqiqi ədədləri varsa ki, a[1]^2 + ... + a[k]^2 ≠ 0, onda a[1] * v[1] + ... + a[k] * v[k] ≠ 0 bərabərsizliyi doğrudur.
Sətirlər üçün standart skalyar vurma və toplama qaydaları istifadə olunur:
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)).
Sıfır sətir 0 = (0, ..., 0).
Giriş məlumatları
Birinci sətir iki ədəd n və m (2 ≤ n ≤ 2 * 10^5, 1 ≤ m ≤ 2 * 10^5) ehtiva edir: matrisdəki sətir və sütunların sayı. Növbəti 2m sətirin hər biri iki ədəd r və c (1 ≤ r ≤ n, 1 ≤ c ≤ m) ehtiva edir, matrisdəki 1-lərin mövqelərini təyin edir. Burada r - sətir nömrəsi, c - sütun nömrəsi. Siyahıda göstərilməyən bütün hüceyrələr sıfıra bərabərdir. Bütün (r, c) cütlərinin fərqli olduğu və hər sütunda dəqiq iki 1 olduğu təmin edilir.
Çıxış məlumatları
Bir ədəd çıxarın: matrisin rütbəsi.
