CF457F.An easy problem about trees

Pieguy and Piegirl are playing a game. They have a rooted binary tree, that has a property that each node is either a leaf or has exactly two children. Each leaf has a number associated with it.

On his/her turn a player can choose any two leafs that share their immediate parent, remove them, and associate either of their values with their parent, that now became a leaf (the player decides which of the two values to associate). The game ends when only one node (the one that was the root of the tree) is left.

Pieguy goes first, and his goal is to maximize the value that will be associated with the root when the game ends. Piegirl wants to minimize that value. Assuming that both players are playing optimally, what number will be associated with the root when the game ends?

Pieguy 和 Piegirl 正在进行一场游戏。他们拥有一棵有根二叉树，该树具有如下性质：每个节点要么是叶子节点，要么恰好有两个子节点。每个叶子节点都关联着一个数值。

在轮到某位玩家时，该玩家可以选择任意两个具有相同直接父节点的叶子节点，将它们移除，并将这两个叶子节点中的任一数值（由该玩家决定选择哪一个）关联到它们的父节点上；此时该父节点变为新的叶子节点。当整棵树只剩下唯一一个节点（即原树的根节点）时，游戏结束。

Pieguy 先手，他的目标是使游戏结束时根节点所关联的数值尽可能大；Piegirl 则希望该数值尽可能小。假设双方均采取最优策略，那么游戏结束时根节点将关联哪个数值？

First line contains a single integer t (1 ≤ t ≤ 100) — number of test cases. Then t test cases follow. Each test case begins with an empty line, followed by a line with a single integer n (1 ≤ n ≤ 250), followed by n lines describing n nodes of the tree. Each of those n lines either contains a non-negative number a__i, indicating a leaf node with value a__i (0 ≤ a__i ≤ 1000) associated with it, or  - 1 followed by integers l and r, indicating a non-leaf node with children l and r (0 ≤ l, r ≤ n - 1). Nodes are numbered from 0 to n - 1. The root is always node 0.

第一行包含一个整数 $t$（$1 \leq t \leq 100$）—— 表示测试用例的数量。随后是 $t$ 个测试用例。每个测试用例以一个空行开始，接着是一行包含单个整数 $n$（$1 \leq n \leq 250$），然后是 $n$ 行，用于描述树的 $n$ 个节点。这 $n$ 行中的每一行要么包含一个非负整数 $a_i$，表示一个值为 $a_i$ 的叶节点（$0 \leq a_i \leq 1000$）；要么包含 $-1$ 后跟两个整数 $l$ 和 $r$，表示一个具有左右子节点 $l$ 和 $r$ 的非叶节点（$0 \leq l, r \leq n - 1$）。节点编号从 $0$ 到 $n - 1$。根节点始终为节点 $0$。

For each test case print one line with one integer on it — the number that will be associated with the root when the game ends.

对于每个测试用例，输出一行，包含一个整数——游戏结束时根节点所关联的数字。