Զբոսանք

Էմիլը ապրում է մի հիասքանչ երկրում որտեղ քաղաքները համարակալված են 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: 0.6 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue