Հեծանվային թեքություններ
Էմիլը ցանկանում է հեծանվով ճանապարհորդել քաղաք 1-ից մինչև քաղաք n, սակայն քաղաքները կապող ճանապարհները լրացուցիչ դժվարություններ են առաջացնում։ Յուրաքանչյուր ճանապարհ կա՛մ վերելք է, կա՛մ վայրէջք։ Երբ Էմիլը վերելքից անցնում է վայրէջքի (կամ հակառակը), նա ստիպված է փոխել հեծանվի փոխանցման աստիճանը (gear)՝ հարմարավետ ճանապարհորդությունը պահպանելու համար։ Էմիլին հետաքրքրում է, թե ի نهایت քանի անգամ նա նվազագույնը ստիպված կլինի փոխել հեծանվի փոխանցման աստիճանը ճանապարհին՝ քաղաք 1-ից մինչև քաղաք n հասնելու համար։
Ծրագիրը պետք է հաշվի այդ նվազագույն փոխումների քանակը և տպի այն:
Մուտք
Մուտքի առաջին տողում տրված են երկու ամբողջ թվեր n և m (2 ≤ n ≤ 100000, 1 ≤ m ≤ 100000), որոնք նշում են քաղաքների և ճանապարհների քանակը, համապատասխանաբար։
Հաջորդ m տողերից յուրաքանչյուրում տրվում են երկու ամբողջ թվեր և (, ), որոնք ցույց են տալիս, որ կա ճանապարհ, որը կապում է և քաղաքները։ -ից տանող ճանապարհը վերելք է, իսկ -ից տանող ճանապարհը՝ վայրէջք։
Ելք
Ծրագիրը պետք է տպի մեկ ամբողջ թիվ, որը ցույց է տալիս, թե Էմիլը նվազագույնը քանի անգամ պետք է փոխի հեծանվի փոխանցման աստիճանը քաղաք 1-ից մինչև քաղաք n հասնելու համար։
Օրինակներ
Մուտք | Ելք |
|---|---|
5 5 | 1 |
3 3
| 0 |
Constraints
Time limit: 6 seconds
Memory limit: 512 MB
Output limit: 1 MB