Նոր ճանապարհներ
Նազարի թագավորության տարիներին այդպես էլ ճանապարհները չկարգավորվեցին։ Բոլոր ճանապարհները նեղ էին և միակողմանի։ Այդ պատճառով կարող էին լինել քաղաքների զույգեր, որ մի քաղաքից մյուսը հնարավոր չէր հասնել։ Նազարին հաջորդած Բայթազար թագավորը որոշեց շտկել դրությունը՝ կառուցել լրացուցիչ միակողմանի ճանապարհներ, որ հնարավոր լինի ցանկացած քաղաքից ցանկացած քաղաք հասնել։ Բնականաբար, նա ցանկանում է, որ նոր ճանապարհների քանակը մինիմալ լինի։ Պահանջվում է գրել ծրագիր, որը գտնում է այդ քանակը։
Մուտքային տվյալներ
Առաջին տողում տրված են քաղաքների
n (1 ≤ n ≤ 20000) քանակը և ճանապարհների m (1 ≤ m ≤ 50000) քանակը։ Հաջորդ m տողերից յուրաքանչյուրում տրված են երկու x, y (1 ≤ x, y ≤ n, x ≠ y) թվեր, նշանակում է գոյություն ունի x համարի քաղաքից y համարի քաղաք տանող միակողմանի ճանապարհ։Ելքային տվյալներ
Ելքում պետք է արտածել մեկ թիվ՝ մինիմալ ճանապարհների քանակը, որ պետք է կառուցել։
Օրինակներ
Մուտք | Ելք |
3 2
1 2
1 3 | 2 |
3 0 | 3 |
Աղբյուրը. Հանրապետական 2019
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB