N puncte numerotate de la 1 la N sunt aşezate pe cerc, în sensul acelor de ceasornic, în ordine strict crescătoare.
Există M segmente de dreaptă diferite care unesc M perechi de puncte dintre cele N date. Cele două puncte care formează orice pereche sunt distincte.
Distanţele dintre două puncte succesive sunt alese astfel încât să nu existe 3 sau mai multe segmente care trec printr-un acelaşi punct interior cercului.
Cerinţă
Cunoscându-se numărul de puncte, numărul de perechi şi perechile de puncte care vor fi unite, se cere să se determine numărul P de puncte de intersecţie formate de acestea în interiorul cercului (punctele de intersecţie aflate chiar pe cerc nefiind luate în considerare).
Date de intrare
Fişierul de intrare cerc.in conţine pe prima linie două numere naturale N şi M despărţite printr-un spaţiu, numere reprezentând numărul de puncte şi respectiv numărul de segmente. Pe următoarele M linii se află câte o pereche de numere naturale distincte pi1, pi2 despărţite prin câte un spaţiu, numere reprezentând capetele câte unui segment.
Date de ieşire
Fişierul de ieşire cerc.out va conţine o singură linie pe care va fi scris un singur număr natural P reprezentând numărul total de puncte de intersecţie formate în interiorul cercului. Dacă acest număr depăşeşte 999999, atunci se va scrie numărul format numai din ultimele sale 6 cifre.
Restricţii
1 ≤ N ≤ 500
0 ≤ M < 125000
1 ≤ pi1 < pi2 ≤ N, oricare 1≤i≤M
Nu există două perechi pi1,pi2 identice.
Exemple
cerc.in
cerc.out
Explicaţii
5 6
1 2
1 3
1 4
2 4
3 5
4 5
3
S-au format în interiorul cercului 3 puncte de intersecţie (marcate prin cerculeţe pe figura alăturată)
