Meme Tournament

You work for a small ad agency trying to create the next viral meme. Every meme is measured by two real‐number scales, called xanthochromism and yellowishness, with values \(x\) and \(y\) respectively. The quality of a meme is defined as its squared Euclidean distance from the Base Meme \((0,0)\), i.e. \(x^2+y^2\).

To generate a new meme, you run a tournament. The tournament is given as a rooted tree. The leaves represent the input memes with their \(x,y\) values, and each internal node represents an online vote among its children. At a vote node with \(k\) children having meme values \((x_1,y_1),\ldots,(x_k,y_k)\), the process works as follows: exactly one child is chosen as the winner. Then, a new meme is produced with

[ x = \sum_{i=1}^{k} w_i \cdot x_i, \qquad \text{and} \qquad y = \sum_{i=1}^{k} w_i \cdot y_i, ]

where the weight (w_i = 1) if the (i^{th}) child wins the vote and (w_i = -1) otherwise. This means the new meme is computed as

[ (x,y) = 2,(x_{\text{winner}},y_{\text{winner}}) - \sum_{i=1}^{k} (x_i,y_i). ]

The tournament proceeds in this manner from the leaves up to the root. Finally, the meme produced at the root is declared the ultimate meme. Your task is to determine the largest possible quality (i.e. squared distance from \((0,0)\)) that can result from the tournament if you choose the winners at each vote optimally.

Observation: A short analysis shows that regardless of the tree structure, the tournament forces the final result to be of the form

[ \textbf{M} = 2,v_i - T, ]

where (T) is the sum of all leaf meme vectors and (v_i) is the meme vector from one particular leaf. (In fact, the constraints force exactly one leaf to have a coefficient of +1 and all other leaves a coefficient of -1.) Thus, if there are (L) leaves and their values are (v_1, v_2, \dots, v_L) with (T = \sum_{i=1}^{L} v_i), then the maximum quality is

[ \max_{1 \le i \le L} ; |2v_i - T|^2. ]

inputFormat

The first line contains a single integer \(n\) representing the number of nodes in the tournament tree. The nodes are numbered from 1 to \(n\), and node 1 is the root.

Then \(n\) lines follow. For the \(i^{th}\) line:

• If the node is an internal vote node, the line begins with an integer \(k\) (\(k \ge 1\)) followed by \(k\) space‐separated integers representing the indices of its children.
• If the node is a leaf (an input meme), the line begins with 0 followed by two integers \(x\) and \(y\) indicating its meme values.

You may assume the tree is valid and all nodes are reachable from the root.

outputFormat

Output a single integer — the largest possible quality (i.e. \(x^2+y^2\)) that can be achieved at the root.

sample

1
0 3 4

25