ŠIOM — Beždžionių planetos iškilimas

Laiko ribojimas: 0.5s

Atminties ribojimas: 256MB

Language:
Source file:
Jei norite pateikti savo sprendimą - prisijunkite.

Beždžionių planetos iškilimas

Beždžionių planetos lyderiai ruošiasi priimti svečius iš kitų planetų ir dėl to nutarė pagerinti susisiekimą tarp miestų. Beždžionių planeta, taip pat kaip ir žemė, yra plokščia ir visi miestai yra išsidėstę vakariniame ir rytiniame kraštuose. Vakariniame krašte yra $n$ miestų sunumeruotų nuo $1$ iki $n$ iš šiaurės į pietus. Rytiniame krašte yra $m$ miestų taip pat sunumeruotų nuo $1$ iki $m$ iš šiaurės į pietus.

Planetos lyderiai nutarė pastatyti $k$ greitkelių tarp vakarinių ir rytinių miestų. Kiekvienas greitkelis yra tiesi linija tarp vieno vakarinio ir vieno rytinio miestų.

Kelininkai sutarė, jog sudėtingiausia projekto dalis bus kelių susikirtimų statyba. Vienoje vietoje gali susikirsti tik du keliai. Jūsų užduotis - apskaičiuoti susikirtimų tarp kelių skaičių.

Pradiniai duomenys

Pirmoje eilutėje duoti trys skaičiai $n$ , $m$ ir $k$ . $(1\\leqn,m\\leq1000,1\\leqk\\leqn*m)$ - miestų skaičius vakarinėje dalyje, miestų skaičius rytinėje dalyje ir greitkelių skaičius.

Sekančiose $k$ eilučių duota po du skaičius $a_i,b_i$ $(1\\leqa_i\\leqn,1\\leqb_i\\leqm)$ - reiškiančius, kad tarp vakariniame krašte esančio miesto $a_i$ ir rytiniame krašte esančio miesto $b_i$ statomas greitkelis.

Rezultatai

Išveskite vieną skaičių - kiek bus greitkelių susikirtimų.

Pavyzdys

Duomenys	Rezultatai
3 4 4 1 4 2 3 3 2 3 1	5

Šeštadieninė informatikos olimpiadininkų mokykla

Beždžionių planetos iškilimas

Pradiniai duomenys

Rezultatai

Pavyzdys