Module: Spanning Trees: Algoritmo di Kruskal

Problem

Besi si trova su una rete di N (2≤N≤10⁵) vertici etichettati 1…N e 2N portali etichettati 1…2N. Ogni portale collega due diversi vertici u e v (u≠v). Un insieme di portali può connettere una coppia di vertici.
Ogni vertice v è adiacente a quattro diversi portali. L'elenco dei portali di v è dato da pv=[p_v,1,p_v,2,p_v,3,p< sub>v ,4].

La tua posizione attuale può essere rappresentata da una coppia ordinata (vertice attuale,portale attuale); cioè una coppia (v,p_v,i) dove 1≤v≤N e 1≤i≤4. Puoi utilizzare una delle seguenti operazioni per modificare la tua posizione attuale:

Cambia il vertice corrente spostandoti attraverso il portale corrente.
Cambia portale corrente. Ad ogni vertice, i primi due portali dell'elenco sono accoppiati e anche gli ultimi due portali dell'elenco sono accoppiati. Quindi, se il tuo stato attuale è (v,p_v,2), puoi passare all'uso del portale (v,p_v,1) e viceversa. Allo stesso modo, se la tua posizione attuale è (v,p_v,3) puoi passare al portale (v,p_v,4) e viceversa. nessun altro passaggio è consentito (ad es. non è possibile passare dal portale pv,2 al portale) p_v,4).
Ci sono 4 N stati diversi in totale. Sfortunatamente, potrebbe non essere possibile raggiungere uno stato da qualsiasi stato mediante una sequenza di determinate operazioni. Pertanto, per il costo di lune cv (1≤c_v≤1000), puoi riorganizzare l'elenco dei portali adiacenti a v, nell'ordine che preferisci. Successivamente, i primi due portali nell'elenco vengono combinati in una coppia e gli ultimi due portali in un'altra coppia.

Ad esempio, se riorganizzi i portali di v nell'ordine [p_v,3,p_v,1,p_v,2, p_v,4], questo significa. cosa succede se sei in cima v,

Se ti trovi nel portale p_v,1, puoi passare al portale p_v,3 e tornare indietro
Se ti trovi nel portale p_v,2, puoi passare al portale p_v,4 e tornare indietro
Ora non puoi passare dal portale p_v,1 a p_v,2, o dal portale p_v,3 al portale p _v,4 e viceversa.
Calcolare il numero minimo di lune necessarie per modificare la rete in modo tale da rendere ogni stato raggiungibile da ogni stato. È garantito che i dati del test siano costruiti in modo tale che ci sia almeno un modo per modificare la rete in questo modo.

Inserisci: 
La prima riga contiene N.
Ognuna delle successive N righe descrive un vertice. La stringa v+1 contiene 5 interi separati da spazio c_v,p_v,1,p_v,2,p_{v ,3},p_v,4.
È garantito che per ogni v tutti i p_v,1,p_v,2,p_v,3,p_{v, 4} sono distinti e ogni portale appare negli elenchi di esattamente due vertici.

Uscita: 
Una riga contiene il numero minimo di lune necessarie per modificare la rete per rendere ogni stato raggiungibile da un altro stato.
 

Esempi

#	Input	Uscita	Spiegazione
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	È sufficiente scambiare le liste dei vertici 1 e 4. Ciò richiede c1+c4=13 muns. Le permutazioni sono: p1=[1,9,4,8] e p4=[7,4,6,3].