Կամուրջների կառուցում
Քաղաքի միջով հենց կենտրոնում հոսում է գեղեցիկ մի գետ։ Քաղաքային իշխանությունները ցանկանում են օգտակար կամուրջներ կառուցել, որպեսզի մարդիկ այլևս նավակներով չանցնեն գետը, ինչը այնքան էլ հարմար չէ։
Հայտնի է դարձել, որ կա n կոորդինատների զույգ, որոնց միջև հնարավոր է կամուրջ կառուցել։ Միևնույն ժամանակ կա պահանջ, որ կամուրջները չխաչվեն (մեկ կամուրջը չի կարող անցնել մյուսի վրայով), թեև կարելի է օգտագործել նույն սկզբնական կամ վերջնական կետերը։
Ելնելով այդ n զույգերից՝ անհրաժեշտ է պարզել, թե առավելագույնը քանի կամուրջ կարելի է կառուցել՝ չխախտելով սահմանված պայմանները։
Մուտք
Մուտքի առաջին տողում տրված է մեկ ամբողջ թիվ n (1 ≤ n ≤ 100 000)։
Հաջորդ n տողերում նշված են ամբողջ թվերից բաղկացած զույգեր , որոնք ներկայացնում են հնարավոր կամուրջների կոորդինատները (1 ≤ ≤ )։
Ելք
Ծրագիրը պետք է տպի մեկ ամբողջ թիվ, որը ցույց է տալիս առավելագույն քանակի կամուրջները, որ հնարավոր է կառուցել։
Օրինակներ
Մուտք | Ելք |
|---|---|
4 2 6 5 4 8 1 10 2 | 2 |
6 1 3 2 4 3 5 4 6 5 1 6 2 | 4 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB