Module: Spanning Trees: Algoritmo de Kruskal

Problem

Besi está localizado em uma rede de N (2≤N≤10⁵) vértices rotulados como 1…N e 2N portais rotulados como 1…2N. Cada portal conecta dois vértices diferentes u e v (u≠v). Um conjunto de portais pode conectar algum par de vértices.
Cada vértice v é adjacente a quatro portais diferentes. A lista de portais de v é dada por pv=[p_v,1,p_v,2,p_v,3,p< sub>v ,4].

Sua posição atual pode ser representada por um par ordenado (vértice atual, portal atual); isto é, um par (v,p_v,i) onde 1≤v≤N e 1≤i≤4. Você pode usar uma das seguintes operações para alterar sua posição atual:

Altere o vértice atual movendo-se pelo portal atual.
Alternar portal atual. Em cada vértice, os dois primeiros portais da lista são pareados e os dois últimos portais da lista também são pareados. Portanto, se seu estado atual for (v,p_v,2), você poderá alternar para usar o portal (v,p_v,1) e vice-versa. Da mesma forma, se sua posição atual for (v,p_v,3), você pode alternar para o portal (v,p_v,4) e voltar. nenhuma outra troca é permitida (por exemplo, você não pode mudar de portal pv,2 para portal) p_v,4).
Existem 4N estados diferentes no total. Infelizmente, pode não ser que qualquer estado seja alcançável a partir de qualquer estado por uma sequência de determinadas operações. Portanto, pelo custo de cv (1≤c_v≤1000) luas, você pode reorganizar a lista de portais adjacentes a v, na ordem que desejar. Depois disso, os dois primeiros portais da lista são combinados em um par e os dois últimos portais em outro par.

Por exemplo, se você reorganizar os portais de v na ordem [p_v,3,p_v,1,p_v,2, p_v,4], Isso significa. e se você estiver no top v,

Se você estiver no portal p_v,1, poderá alternar para o portal p_v,3 e voltar
Se você estiver no portal p_v,2, poderá alternar para o portal p_v,4 e voltar
Agora você não pode mudar do portal p_v,1 para p_v,2, ou do portal p_v,3 para o portal p _v,4 e vice-versa.
Calcule o número mínimo de luas necessárias para modificar a rede de forma a tornar cada estado acessível a partir de cada estado. É garantido que os dados de teste sejam construídos de forma que haja pelo menos uma maneira de modificar a rede dessa maneira.

Entrada: 
A primeira linha contém N.
Cada uma das próximas N linhas descreve um vértice. A string v+1 contém 5 inteiros separados por espaço c_v,p_v,1,p_v,2,p_{v ,3},p_v,4.
É garantido que para cada v todo p_v,1,p_v,2,p_v,3,p_{v, 4} são distintos, e cada portal aparece nas listas de exatamente dois vértices.

Saída: 
Uma linha contém o número mínimo de luas necessárias para modificar a rede para tornar cada estado acessível a partir de outro estado.
 

Exemplos

#	Entrada	Saída	Explicação
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	É suficiente trocar as listas dos vértices 1 e 4. Isso requer c1+c4=13 muns. As permutações são: p1=[1,9,4,8] e p4=[7,4,6,3].