CF1687B Railway System

As for the technology in the outside world, it is really too advanced for Gensokyo to even look up to. —Yasaka Kanako, Symposium of Post-mysticism This is an interactive problem. Under the direct supervision of Kanako and the Moriya Shrine, the railway system of Gensokyo is finally finished. GSKR (Gensokyo Railways) consists of $ n $ stations with $ m $ bidirectional tracks connecting them. The $ i $ -th track has length $ l_i $ ( $ 1\le l_i\le 10^6 $ ). Due to budget limits, the railway system may not be connected, though there may be more than one track between two stations. The value of a railway system is defined as the total length of its all tracks. The maximum (or minimum) capacity of a railway system is defined as the maximum (or minimum) value among all of the currently functional system's [full spanning forest](https://en.wikipedia.org/wiki/Spanning_tree#Spanning_forests). In brief, full spanning forest of a graph is a spanning forest with the same connectivity as the given graph. Kanako has a simulator only able to process no more than $ 2m $ queries. The input of the simulator is a string $ s $ of length $ m $ , consisting of characters 0 and/or 1. The simulator will assume the $ i $ -th track functional if $ s_i= $ 1. The device will then tell Kanako the maximum capacity of the system in the simulated state. Kanako wants to know the the minimum capacity of the system with all tracks functional with the help of the simulator. The structure of the railway system is fixed in advance. In other words, the interactor is not adaptive.

N/A

N/A

Here is the graph of the example, satisfying $ l_i=i $ .