Company: Goldman_Sachs_12nov
Difficulty: medium
Optimal Reconstruction Problem Description The army has built an extensive underground tunnel system connecting its bunkers near the country's border areas. Each tunnel connects two bunkers end to end. To make mid-tunnel checkpoints effective, the engineers ensured that the tunnels are built such that there is exactly one unique route between any two bunkers. The distance between two bunkers is defined as the number of tunnels one has to pass through, to reach from one bunker to the other. After some time, the commanders noticed that moving soldiers and supplies between certain distant bunkers was taking too long. To optimize the system, they decided to reconstruct the tunnel network by closing one of the existing tunnels, and opening one new tunnel between two previously unconnected bunkers, while ensuring that : 1) The network of bunkers continues to stay fully connected, as before. 2) There is still exactly one path between any two bunkers, as before. 3) The longest distance between