Module: درختان پوشا: الگوریتم کروسکال

Problem

Besi در شبکه ای از راس N (2≤N≤10⁵) با برچسب 1…N و پورتال 2N با برچسب 1…2N قرار دارد. هر پورتال دو راس مختلف u و v (u≠v) را به هم متصل می کند. مجموعه ای از پورتال ها می توانند چند جفت رئوس را به هم متصل کنند.
هر رأس v مجاور چهار پورتال مختلف است. لیست پورتال های v توسط pv=[p_v,1,p_v,2,p_v,3,p< ارائه شده است. sub>v ,4].

موقعیت فعلی شما را می توان با یک جفت مرتب شده (رأس فعلی، پورتال فعلی) نشان داد. یعنی یک جفت (v,p_v,i) که در آن 1≤v≤N و 1≤i≤4. برای تغییر موقعیت فعلی خود می توانید از یکی از عملیات زیر استفاده کنید:

راس فعلی را با حرکت در پورتال فعلی تغییر دهید.
پورتال فعلی را تغییر دهید. در هر رأس، دو پورتال اول لیست جفت می شوند و دو پورتال آخر لیست نیز جفت می شوند. بنابراین اگر وضعیت فعلی شما (v,p_v,2) است، می توانید از پورتال (v,p_v,1) استفاده کنید و به عقب برگردید. به طور مشابه، اگر موقعیت فعلی شما (v,p_v,3) باشد، می توانید به پورتال (v,p_v,4) بروید و برگردید. هیچ تغییر دیگری مجاز نیست (مثلاً نمی توانید از پورتال pv,2 به پورتال سوئیچ کنید) p_v,4).
در کل 4N ایالت مختلف وجود دارد. متأسفانه، ممکن است هیچ حالتی از هر حالتی با دنباله ای از عملیات داده شده قابل دسترسی نباشد. بنابراین، برای هزینه ماه‌های cv (1≤c_v≤1000)، می‌توانید فهرست پورتال‌های مجاور v را به هر ترتیبی که می‌خواهید مرتب کنید. پس از آن، دو پورتال اول لیست در یک جفت و دو پورتال آخر در یک جفت دیگر ترکیب می‌شوند.

برای مثال، اگر پورتال های v را به ترتیب [p_v,3,p_v,1,p_v,2 مجدداً مرتب کنید، p_v,4]، به این معنی است. چه می شود اگر شما در بالای v،

اگر در پورتال p_v,1 هستید، می توانید به پورتال p_v,3 بروید و برگردید
اگر در پورتال p_v,2 هستید، می توانید به پورتال p_v,4 بروید و برگردید
اکنون نمی توانید از پورتال p_v,1 به p_v,2 یا از پورتال p_v,3 به پورتال p _{بروید v,4} و بالعکس.
حداقل تعداد قمرهای مورد نیاز برای تغییر شبکه را به گونه ای محاسبه کنید که هر حالت از هر ایالت قابل دسترسی باشد. تضمین می شود که داده های آزمایشی به گونه ای ساخته شده اند که حداقل یک راه برای اصلاح شبکه به این روش وجود داشته باشد.

ورودی: 
خط اول حاوی N.
است هر یک از N خطوط بعدی یک راس را توصیف می کند. رشته v+1 شامل 5 عدد صحیح جدا شده با فاصله c_v,p_v,1,p_v,2,p_{v ,3},p_v,4.
تضمین شده است که برای هر v همه p_v,1,p_v,2,p_v,3,p_{v, 4} متمایز هستند و هر پورتال دقیقاً در لیست دو رأس ظاهر می شود.

خروجی: 
یک خط حاوی حداقل تعداد قمرهای مورد نیاز برای تغییر شبکه است تا هر حالت از حالت دیگری قابل دسترسی باشد.
 

نمونه‌ها

<سر> <بدن>

#	ورودی	خروجی	توضیح
1	5 10 1 4 8 9 11 1 2 5 6 12 9 10 2 3 3 4 3 6 7 15 10 8 7 5	13	کافی است لیست های رئوس 1 و 4 را مبادله کنید. این به c1+c4=13 muns نیاز دارد. جایگشت ها عبارتند از: p1=[1,9,4,8] و p4=[7,4,6,3].