CF444A DZY Loves Physics

DZY loves Physics, and he enjoys calculating density. Almost everything has density, even a graph. We define the density of a non-directed graph (nodes and edges of the graph have some values) as follows:  where $ v $ is the sum of the values of the nodes, $ e $ is the sum of the values of the edges.Once DZY got a graph $ G $ , now he wants to find a connected induced subgraph $ G' $ of the graph, such that the density of $ G' $ is as large as possible. An induced subgraph $ G'(V',E') $ of a graph $ G(V,E) $ is a graph that satisfies: - ; - edge  if and only if , and edge ; - the value of an edge in $ G' $ is the same as the value of the corresponding edge in $ G $ , so as the value of a node. Help DZY to find the induced subgraph with maximum density. Note that the induced subgraph you choose must be connected. 

N/A

N/A

In the first sample, you can only choose an empty subgraph, or the subgraph containing only node $ 1 $ . In the second sample, choosing the whole graph is optimal.