Fişierul intrare/ieşire:	cerc4.in, cerc4.out	Sursă	Lot Juniori 2009 - Baraj 4
Autor	Rodica Pintea	Adăugată de	Cezar Mocan •CezarMocan
Timp execuţie pe test	0.075 sec	Limită de memorie	12288 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Cerc4

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 cerc4.in conţine:

• pe prima linie două numere 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, câte o pereche de numere dinstincte p_i1, p_i2 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 cerc4.out va conţine un singur număr 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 ≤ p_i1 ≤ p_i2 ≤ N
• Nu exista doua perechi p_i1 p_i2 identice

Exemplu

Explicaţie

S-au format în interiorul cercului 3 puncte de intersecţie (marcate prin cerculeţe pe figură) 

Cum se trimit solutii?