Tree Data Structures

ID 38132. Portals

Besi is located on a network of N (2≤N≤10⁵) vertices labeled 1…N and 2N portals labeled 1…2N. Each portal connects two different vertices u and v (u≠v). A set of portals can connect some pair of vertices.
Each vertex v is adjacent to four different portals. The list of portals of v is given by pv=[p_v,1,p_v,2,p_v,3,p_{v ,4}].

Your current position can be represented by an ordered pair (current vertex,current portal); that is, a pair (v,p_v,i) where 1≤v≤N and 1≤i≤4. You can use one of the following operations to change your current position:

Change the current vertex by moving through the current portal.
Switch current portal. At each vertex, the first two portals in the list are paired and the last two portals in the list are also paired. So if your current state is (v,p_v,2), then you can switch to use the portal (v,p_v,1) and back. Similarly, if your current position is (v,p_v,3) you can switch to the portal (v,p_v,4) and back. no other switching is allowed (eg you cannot switch from portal pv,2 to portal) p_v,4).
There are 4N different states in total. Unfortunately, it may not be that any state is reachable from any state by a sequence of given operations. Therefore, for the cost of cv (1≤c_v≤1000) moons, you can rearrange the list of portals adjacent to v, in any order you wish. After that, the first two portals in the list are combined into one pair, and the last two portals into another pair.

For example, if you rearrange the portals of v in the order [p_v,3,p_v,1,p_v,2,p_v,4], This means. what if you are at top v,

If you are in the p_v,1 portal, you can switch to the p_v,3 portal and back
If you are in the p_v,2 portal, you can switch to the p_v,4 portal and back
Now you cannot switch from portal p_v,1 to p_v,2, or from portal p_v,3 to portal p_v,4 and vice versa.
Calculate the minimum number of moons required to modify the network in such a way as to make each state reachable from each state. It is guaranteed that the test data is constructed in such a way that there is at least one way to modify the network in this way.

Input: 
The first line contains N.
Each of the next N lines describes a vertex. The string v+1 contains 5 space-separated integers c_v,p_v,1,p_v,2,p_{v ,3},p_v,4.
It is guaranteed that for each v all p_v,1,p_v,2,p_v,3,p_v,4 are distinct, and each portal appears in the lists of exactly two vertices.

Output: 
One line contains the minimum number of moons required to modify the network to make each state reachable from another state.
 

Examples

ID 38135. Routing schemes

Error

ID 38501. LinkedList's Bizarre Adventure

Error