Cerința

Pe o tablă de șah de dimensiune n se află m regine. O regină atacă o altă regină dacă cele două se află pe aceeași linie, coloană sau diagonală și între ele nu se află alte regine. Determinați numărul maxim p de regine care sunt atacate de o aceeași regină și numărul q de regine care atacă p alte regine.

Date de intrare

Fișierul de intrare regine.in conține pe prima linie numerele n m; următoarele m linii conțin perechi i j reprezentând linia și coloana unde se află poziționată o regină.

Date de ieșire

Fișierul de ieșire regine.out va conține pe prima linie numerele p q, separate prin exact un spațiu, reprezentând valorile de mai sus.

Restricții și precizări

• 1 ≤ n ≤ 100
• 1 ≤ m ≤ 500
• 1 ≤ i,j ≤ n
• pe tablă nu există două regine suprapuse

Exemplu:

regine.in

8 9
1 7
2 2 
2 8
4 1
5 2
5 5
5 8
7 2
7 7

regine.out

5 1

Explicație