Nosaukums
Cik četrstūru? (cikche)
Laika limits
0.50s
Atmiņas limits
128.0 MB
Grūtība
44%

Definīcija

Gudrinieks Jānis aiz garlaicības lasa žurnālu "Sejas Grāmata". Tajā viņš atrada sekojošo vizuālu mīklu ar nosaukumu "Tikai 1% no gudrinieku ciema var atrisināt šo mīklu, uzzini vai esi ģēnijs!". Ir uzzīmēti n punkti, katrs no kuriem ir vai nu sarkans, vai nu zils. Daži no punktiem ir savienoti ar nogriežņiem, pie tam nav divu vienādas krāsas punktu, kas savienoti ar nogriezni. Uzdevumā tiek prasīts saskaitīt, cik bildē ir redzami četrstūri, pie tam ir zināms, ka nekādi trīs punkti neatrodas uz vienas taisnes. Kas atrisinās mīklu ātrāk – Jānis vai Jūs? (Jānim datora nav.)

Par četrstūri sauc četrus punktus a, b, c, d tādus, ka pāri a un b, b un c, c un d, d un a ir savienoti ar nogriežņiem. Nogriežņu krustojumus neuzskatām par punktiem.


Ievaddatu raksturojums

Pirmajā rindā doti divi naturāli skaitļi n un m, uzzīmēto punktu skaits un nogriežņu skaits (2 ≤ n ≤ 1 000, 1 ≤ m ≤ 250 000). Punkti ir sanumurēti ar veseliem skaitļiem no 1 līdz n. Tālāk seko m rindas, i-tā no kurām satur divus skaitļus ai un bi (1 ≤ ai bi ≤ nai ≠ bi), punktu, kas savienoti ar i-to nogriezni, numuri. Garantēts, ka nekādi divi punkti nav savienoti ar vairāk kā vienu nogriezni. Garantēts, ka visus punktus var nokrāsot divās krāsās tā, ka nekādi divi vienādas krāsas punkti nav savienoti ar nogriezni.


Izvaddatu raksturojums

Jāizvada viens skaitlis – četrstūru skaits.


Paraugdati

Stdin
6 8
1 2
2 3
5 1
3 5
1 6
5 4
6 3
4 6
Stdout
5

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.