Ești în anul 2121 și vrei să configurezi o rețea de Neuralink. Ai la dispoziție N servere, ale căror IP-uri sunt reprezentate de permutări de lungime M (ale numerelor 0, 1 ... M − 1). Vrei ca rețeaua ta să fie cât de mare, dar în același timp, te temi de potențiale probleme de securitate: dacă un hacker află unul dintre IP-uri, îi va fi ușor să găsească un IP similar. Prin urmare, dintre cele N servere pe care le ai la dispoziție, vrei să alegi cât de multe servere pentru rețeaua ta astfel încât să nu existe două servere cu IP-uri similare. Două IP-uri sunt similare, dacă unul dintre ele poate fi obținut din celălalt prin exact o operație swap (o interschimbare a oricăror două elemente). De exemplu, IP-urile (0, 1, 2) și (1, 0, 2) sunt similare, dar (0, 1, 2) și (1, 2, 0) nu.
Date de intrare
Pe prima linie se află numerele N și M. Pe următoarele N linii se vor regăsi câte M numere, elemente ale matricii p. Linia i a matricii p reprezintă cel de-al i-lea IP (o permutare de lungime M).
Date de ieșire
Pe prima linie se va afișa numărul maxim de IP-uri nesimilare.
Restricții și precizări
1 ≤ N ≤ 2 5001 ≤ M ≤ 5 000- Oricare ar fi
0 ≤ i < n,p[i]este o permutare a numerelor de la0laM − 1 - Oricare ar fi
0 ≤ i < j < n,p[i]șip[j]sunt distincte
Subtask 1 (11 puncte)
N, M ≤ 20
Subtask 2 (30 de puncte)
- Cel mult
20de permutări din celeNsunt similare cu oricare alta dintre celeN N ≤ 1000
Subtask 3 (36 de puncte)
N ≤ 300
Subtask 4 (14 puncte)
N ≤ 1000
Subtask 5 (9 puncte)
- Fără restricții suplimentare.
Exemple
stdin
3 3
0 1 2
2 1 0
1 0 2
stdout
2
stdin
5 5
0 1 2 3 4
1 0 2 3 4
0 1 2 4 3
0 4 2 3 1
4 1 2 3 0
stdout
4
stdin
6 3
0 1 2
0 2 1
1 0 2
1 2 0
2 1 0
2 0 1
stdout
3
Explicații
Pentru primul exemplu, alegem serverele cu IP-urile (2, 1, 0) și (1, 0, 2). Nu putem alege serverul (0, 1, 2), deoarece IP-ul său este similar cu ale celorlalte 2.
Pentru cel de-al doilea exemplu, putem alege toate IP-urile în afară de primul.
Pentru cel de-al treilea exemplu, putem selecta IP-urile (0, 1, 2), (1, 2, 0), (2, 0, 1).