Դատարկ սենյակները

Դավիթը և Էմիլը բարկացել են Ալեքսի և Արայիի վրա և նետել նրանց դատարկ սենյակներից և գունավոր դռներից կազմված մի լաբիրինթոս։ Լաբիրինթոսը կարելի է նկարագրել, որպես ուղղորդված ացիկլիկ (ցիկլեր չունեցող) գրաֆ, կազմված n գագաթներից և 2n կողերից։ Կողերը համարակալված են 0-ից մինչև 2n - 1 թվերով: i-րդ կողը ներկված է ⌊ i/2 ⌋ համարի գույնով։ Արային շատ է սիրում array-ներ, սակայն դա չի օգնի նրանց այս լաբիրինթում։ Որպեսզի նրանք կարողանան դուրս գալ լաբիրինթից, նրանք պետք է գտնեն այնպիսի ճանապարհ, որտեղ mex ֆունկցիայի արժեքը այդ ճանապարհի կողերի գույների համարների վրա կիրառելիս, առավելագույն հնարավորն է։ Սակայն Ալեքսը և Արայիին դեռ մի փոքր զարմացած են, այդ իսկ պատճառով որոշել են ձեզանից օգնություն խնդրել։ Օգնեք Ալեքսին և Արայիին, որպեսզի նրանք կարողանան դուրս գալ լաբիրինթոսից։

Սահմանենք mex ֆունկցիայի արժեքը ոչ բացասական ամբողջ թվերից կազմված բազմության վրա, որպես ամենափոքր ոչ բացասական ամբողջ թիվ, որ բացակայում է տվյալ բազմությունից։ Օրինակ՝ mex(0, 1, 3, 7) = 2:

Մուտքային տվյալներ

Առաջին տողում տրված է մեկ բնական թիվ n (2 ≤ n ≤ 1000), գագաթների քանակը։

Հաջորդ 2n տողերում տրված են կողերի նկարագրությունները, որոնք համարակալված են 0-ից մինչև 2n - 1 թվերով։ Մասնավորապես i-րդ համարի կողին համապատասխանող տողում տրված է երկու ամբողջ թիվ ai և bi (1 ≤ ai < bi ≤ n), որը նշանակում է, որ ai համարի գագաթը միացված է bi համարի գագաթին ⌊ i/2 ⌋ համարի գույն ունեցող ուղղորդված կողով։

Ելքային տվյալներ

Արտածել մեկ թիվ՝ mex ֆունկցիայի առավելագույն հնարավոր արժեքը, տրված գրաֆի ճանապարհները դիտարկելիս։

Օրինակ

Բացատրություն

mex ֆունկցիայի առավելագույն արժեքը ստացվում է 1->2->3->4 (կողերի արժեքները համապատասխանաբար 0, 2, 1) ճանապարհը դիտարկելիս, mex(0, 1, 2) = 3:

Ենթախնդիրներ

• Ենթախնդիր 0 (0 միավոր) օրինակը,

• Ենթախնդիր 1 (10 միավոր) երաշխավորում է, որ գոյություն ունի առավելագույն mex ունեցող ճանապարհ, որտեղ կողերի գույների համարները հանդիպում են աճման կարգով,

• Ենթախնդիր 2 (15 միավոր) n ≤ 10,

• Ենթախնդիր 3 (20 միավոր) n ≤ 18,

• Ենթախնդիր 4 (25 միավոր) n ≤ 100,

• Ենթախնդիր 5 (30 միավոր) լրացուցիչ սահմանափակումներ չկան