Թաքցված խնդիր
|Այս խնդիրը թաքցված է խմբագրական խրհրդի անդամի կողմից քանի որ կամ այն ոչ ճիշտ լեզվով է գրված,|կամ թեստային տվյալներն են սխալ, կամ խնդրի ձևակերպումը պարզ չէ։|

ZH2014F - Ամուսնություն

Շատ վաղուց մի հեռավոր երկրում իմաստուն թագավոր էր իշխում։ Նա ուներ, ոչ ավել, ոչ պակաս՝ M աղջիկ։ Ահա եկավ դստրերին ամուսնացնելու ժամանակը, և թագավորը N հարևան երկրներ սուրհանդակներ ուղարկեց։ Այդ լուրը լսելուն պես յուրաքանչյուր երկրից մի արքայազն եկավ։

Լինելով իր դուստրերի կարծիքը հաշվի առնող սիրող հայր, թագավորը առաջին հերթին պահանջեց արաքայազներին շարվել մի շարքով, համարակալեց նրանց 1-ից N թվերով, և հարցրեց իր աղջիկներից յուրաքանչյուրին, թե երիտասարդներից որ մեկի հետ նա կցանկանա ամուսնանալ։

Այդ երկրի թագավորը լավ մաթեմատիկական կրթություն ուներ, և նրա համար դժվար չէր այդ ինֆորմացիայի հիման վրա պարզել, հնարավոր է, արդյոք, իր դուստրերից յուրաքանչյուրին համապատասխանեցնել իր հավանած արքայազներից մեկին։ Բայց երկրի տրիրակալի պրպտուն միտքը տարվեց այսպիսի հարցով. Քանի՞ (L, R) (1<=L<=R<=N) զույգ գոյություն ունի, այնպսին, որ L-ից մինչև R-ը ներառյալ համարներով երիտասարդներից հնարավոր լինի դստրերից յուրաքանչյուրի համար մեկական փեսացու ընտրել։

Օգնեք թագավորին գտնել իր հարցի պատասխանը։

Մուտք

Առաջին տողում տրված են երեք ամբողջ N, M և K թվեր (1<=N<=30000, 1<=M<=2000, 1<=K<=min(N*M, 100000)), համապատասխանաբար, պատանիների քանակը, աղջիկների քանակը և այն տողերի քանակը, որոնցում նկարագրվում են աղջիկների նախասիրությունները։

Հաջորդ K տողերից յուրաքանչյուրում տրված են երկու ամբողջ Ai և Bi ամբողջ թվեր (1<=Ai<=N, 1<=Bi<=M), որոնք նշանակում են, որ Bi աղջկան Ai արքայազնը դուր է գալիս։ Բոլոր գրառումները տարբեր են։

Ելք

Արտածեք մի թիվ՝ խնդրի պայմաններին բավարարող (L, R) զույգերի քանակը։

Օրինակ

Մուտք.
5 3 7
1 1
1 2
1 3
2 3
3 2
4 2
5 1
Ելք. 4

Դիտողություն
Խնդրի պայմաններին բավարարում են (1, 3), (1, 4), (1, 5) և (2, 5) զույգերը։


Ավելացրեց.Andreasyan
Ամսաթիվ.2015-01-08
Ժամանակի սահմանափակումը.1s
Ծրագրի տեքստի սահմանափակումը.50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Լեզուներ.C CSHARP C++ 4.3.2 CPP CPP14 JAVA PAS-GPC PAS-FPC PYTHON3
Աղբյուրը.Ժաուտիկովյան 2014

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.