Սարդոստյան
Պարոն Սարդոստյանը տարածաշրջանում սարդոստայնների աﬔնաﬔծ ցանցի տերն է։ Վերջին շրջանում նրա գործերը շատ լավ են ընթանում, և ճիշտ ժամանակն է նոր սարդոստայն հիﬓելٳ։ Այս անգամ պրն․ Սարդոստյանը որոշել է սարդոստայնը կառուցել ծառի (առանց ցիկլերի կապակցված գրաֆ) տեսքով։ Նա արդեն ունի դրա նախագիծը։ Այն պետք է ունենա N հատ հատում, որոնք համարակալված են 1-ից N թվերով, և հատուﬓերը ﬕացնող աﬔն լար պետք է լինի համապատասխան երկարության (արտահայտված ﬕլիﬔտրերով)։ Սակայն պրն ․ Սարդոստյանը չափազանց զբաղված է և այս գործին կարող է հատկացնել ընդաﬔնը T վայրկյան։ Նա հասկանում է, որ հնարավոր է չհասցնի կառուցել ամբողջ սարդոստայնը և «խնդրում» է ձեզ պարզել, թե աﬔնաշատը քանի լար կարող է կառուցել։ Լարը կառուցելու համար անհրաժեշտ է գոնե ﬔկ անգամ անցնել դրա վրայով (լարը մասամբ կառուցել չի կարելի):
Պրն․ Սարդոստյանը այս պահին գտնվում է 1 համարով հատման վրա և աﬔն վայրկյանում կարող է անցնել 1 ﬕլիﬔտր։ Նա դեռ համոզված չէ սարդոստայնի նախագծի և հատկացվելիք ժամանակի հարցում, այդ պատճառով պետք է պատասխանել S հատ տարբերակի։ Ավելի լավ է լուծեք այս խնդիրը, եթե չեք ուզում հիասթափեցնել տարածաշրջանի աﬔնաազդեցիկ սարդին։
Մٳտքային տվյալներ
Առաջին տողում տրված է նախագծերի S (1 ≤ S ≤ 10) քանակը։ Յուրաքանչյուր մուտքային տվյալների առաջին տողում տրված է հատուﬓերի N (2 ≤ N ≤ 1000) քանակը և առկա T (1 ≤ T ≤ 10 ) վայրկյանը։ Հաջորդ N-1 տողերում տրված են v, u, w (1 ≤ v, u ≤ n, 1 ≤ w ≤ 10 ) թվերի եռյակներ, որտեղ u-ն և v-ն հատուﬓերի համարներն են, իսկ w-ն՝ լարի երկարությունը։
Ելքային տվյալներ
Պետք է արտածել S հատ թիվ` յուրաքանչուٳր նախագծի համար աﬔնաշատը քանի լար կարող է կառուցվել։
Օրինակ
Մուտք | Ելք |
|---|---|
2 5 7 1 2 1 1 3 2 2 4 1 2 5 1 5 8 1 2 1 1 3 2 2 4 1 2 5 1 | 3 4 |
Ենթախնդիրներ
Ենթախնդիր 0 (0 ﬕավոր) Օրինակները,
Ենթախնդիր 1 (5 ﬕավոր) Սարդոստայնը շղթա է (գոյություն ունեն երկու հատուﬓեր, որոնց իրար ﬕացնող ճանապարհի վրա ընկած են ﬓացած բոլոր հատուﬓերը) և բոլոր լարերի երկարությունը 1 է։,
Ենթախնդիր 2 (9 ﬕավոր) Սարդոստայնը շղթա է,
Ենթախնդիր 3 (5 ﬕավոր) Սարդոստայնը աստղ է (գոյություն ունի հատում, որին ﬔկական լարով ﬕացված են ﬓացած բոլոր հատուﬓերը) և բոլոր լարերի երկարությٳնը 1 է,
Ենթախնդիր 4 (9 ﬕավոր) Սարդոստայնը աստղ է,
Ենթախնդիր 5 (21 ﬕավոր) Բոլոր լարերի երկարությունները 1 են,
Ենթախնդիր 6 (19 ﬕավոր) N ≤ 100 ,
Ենթախնդիր 7 (32 ﬕավոր) Հավելյալ սահմանափակٳﬓեր չկան։
Constraints
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB