Module: Genişleyen Ağaçlar: Kruskal'ın Algoritması

Problem

Besi, 1…N olarak etiketlenmiş N (2≤K≤10⁵) köşelerden ve 1…2N olarak etiketlenmiş 2N portallardan oluşan bir ağ üzerinde bulunur. Her portal, u ve v (u≠v) olmak üzere iki farklı köşeyi birbirine bağlar. Bir dizi portal, bazı köşe çiftlerini birbirine bağlayabilir.
Her köşe v, dört farklı portala bitişiktir. v portallarının listesi pv=[p_v,1,p_v,2,p_v,3,p< tarafından verilmiştir. alt>v ,4].

Geçerli konumunuz sıralı bir çiftle temsil edilebilir (mevcut tepe noktası, mevcut portal); yani, 1≤v≤N ve 1≤i≤4 olan bir çift (v,p_v,i). Mevcut konumunuzu değiştirmek için aşağıdaki işlemlerden birini kullanabilirsiniz:

Geçerli portalda ilerleyerek geçerli tepe noktasını değiştirin.
Mevcut portalı değiştir. Her tepe noktasında, listedeki ilk iki portal ve listedeki son iki portal da eşleştirilir. Dolayısıyla, mevcut durumunuz (v,p_v,2) ise, portalı (v,p_v,1) kullanmaya geçebilir ve geri dönebilirsiniz. Benzer şekilde, mevcut konumunuz (v,p_v,3) ise portala (v,p_v,4) geçebilir ve geri dönebilirsiniz. başka geçişe izin verilmez (ör. portal pv,2'den portala geçiş yapamazsınız) p_v,4).
Toplamda 4N farklı durum vardır. Ne yazık ki, herhangi bir duruma herhangi bir durumdan belirli bir işlemler dizisi ile ulaşılamayabilir. Bu nedenle, cv (1≤c_v≤1000) ay maliyeti karşılığında v'ye bitişik portalların listesini istediğiniz sırayla yeniden düzenleyebilirsiniz. Bundan sonra, listedeki ilk iki portal bir çiftte ve son iki portal başka bir çiftte birleştirilir.

Örneğin, v portallarını [p_v,3,p_v,1,p_v,2 sırasına göre yeniden düzenlerseniz, p_v,4], Bu demektir. ya zirvedeysen v,

p_v,1 portalındaysanız, p_v,3 portalına geçebilir ve geri dönebilirsiniz
p_v,2 portalındaysanız, p_v,4 portalına geçebilir ve geri dönebilirsiniz
Artık p_v,1 portalından p_v,2'ye veya p_v,3 portalından p _{portalına geçiş yapamazsınız v,4} ve tersi.
Ağı, her bir durumdan her bir duruma erişilebilir olacak şekilde değiştirmek için gereken minimum uydu sayısını hesaplayın. Test verilerinin, ağı bu şekilde değiştirmenin en az bir yolu olacak şekilde yapılandırılması garanti edilir.

Giriş: 
İlk satır N içerir.
Sonraki N satırın her biri bir tepe noktasını tanımlar. v+1 dizisi 5 boşlukla ayrılmış tamsayı içerir c_v,p_v,1,p_v,2,p_{v ,3},p_v,4.
Her v için tüm p_v,1,p_v,2,p_v,3,p_{v, 4} farklıdır ve her portal tam olarak iki köşenin listelerinde görünür.

Çıktı: 
Bir satır, her bir duruma başka bir durumdan erişilebilmesini sağlamak için ağı değiştirmek için gereken minimum ay sayısını içerir.
 

Örnekler

#	Girdi	Çıktı	Açıklama
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 ve 4. köşe listelerini değiştirmek yeterlidir. Bu, c1+c4=13 muns gerektirir. Permütasyonlar şunlardır: p1=[1,9,4,8] ve p4=[7,4,6,3].