Զբոսանք
Էմիլը ապրում է մի հիասքանչ երկրում որտեղ քաղաքները համարակալված են
1ից N թվերով։ Էմիլը սիրում է ճամփորդել, բայց ցավոք բոլոր ճանապարհները փակ են։ Բարեբախտաբար ճանապարհները աստիճանաբար բացվում են, բայց այնպես, որ ցիկլ չի առաջանում։ Բացվելու ընդացքում Էմիլին հետաքրքրում է, եթե նա գտնվում է x քաղաքում, ապա ամենաքիչը քանի ժամում նա կհասցնի այցելել բոլոր հասանելի քաղաքները։ Ֆորմալ տեղի է ունենում Q իրադարձություն, կամ 1 x y տեսքի, որը նշանակում է xից y ճանապարհ է բացվում (այնպես որ ամեն պահի համապատասխան գրաֆը անտառ է), որը Էմիլը կարող է անցնել 1 ժամում, կամ 2 x տեսքի, որը նշանակում է Էմիլը ուզում է իմանալ x քաղաքից սկսելու դեպքում ամենաքիչը ինչքան ժամանակում կկարողանա այցելել բոլոր հասանելի քաղաքները։Մուտքային տվյալներ
Առաջին տողում տրված են երկու բնական թվեր
N, Q (1 ≤ N, Q ≤ 500000)։ Հաջորդ տողերում տրված են Q հատ հարցում վերոհիշյալ ձևով։Ելքային տվյալներ
Ելքում ամեն երկրորդ տեսակի հարցման համար պետք է արտածել մինիմալ ժամերի քանակը։
Օրինակ
Մուտք | Ելք |
5 8
1 1 2
2 1
1 2 3
2 2
1 2 4
2 4
1 4 5
2 4 | 1
3
4
6 |
Բացատրություն
երկրորդ հարցման ժամանակ 1ին քաղաքից հասանելի է միայն 2րդ քաղաքը որին հասնելու համար անհրաժեշտ է 1 ժամ, չորորդ հարցման ժամանակ 2րդ քաղաքից հասանելի են 1ին և 3րդ քաղաքները, սիզբից պետք է գնալ դրանցից որևէ մեկը հետո վերադառնա 2րդ քաղաք այնուհետև գնալ մյուս չայցելված քաղաքը ծաղսելով 3 ժամ:
Ենթախնդիրներ
- Ենթախնդիր 0 (0 միավոր) Օրինակը,
- Ենթախնդիր 1 (13 միավոր)
- Ենթախնդիր 2 (27 միավոր) ամեն պահի գրաֆը իրենից ներկայացնում է շղթաներ,
- Ենթախնդիր 3 (7 միավոր) ամեն պահի գրաֆը իրենից ներկայացնում է առավելագույնը մեկ աստղ և մեկուսացված գագաթներ,
- Ենթախնդիր 4 (15 միավոր)
- Ենթախնդիր 5 (38 միավոր) լրացուցիչ սահմանափակումներ չկան
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB