描述

John 的大学将举办一场编程竞赛，现在正在征集题目。John 想为此次竞赛贡献一道题目。题目出完后，他在验证程序员输出时遇到了麻烦。对于大多数编程题，你只需将程序员的输出与正确答案逐字比较：若完全相同则输出正确，否则错误。但本题存在多种正确答案，它们在文本上可能各不相同。因此 John 必须编写一个程序来验证程序员的输出（称为“特殊评测程序”）。很快，他发现编写特殊评测程序对他来说太难，于是向你求助。

下面是 John 原始题目的描述：

原始问题 /* 改编自 “Help the problem setter”, Ulm Local 2005 */ 我们按如下方式递归地定义二叉搜索树（BST）： 空树（无节点）是二叉搜索树； 每棵非空二叉搜索树都有一个根节点，节点标记为整数，并且有两棵二叉搜索树作为根的左右子树； 左子树中所有节点的标记都小于根的标记； 右子树中所有节点的标记都大于根的标记。 给定这样的二叉搜索树，可使用如下搜索过程定位树中某个节点：从根节点开始，比较当前节点的标记与目标标记。如果相同，则找到目标节点；否则，若目标标记较小，则在左子树中搜索，否则在右子树中搜索。 某节点的访问频率是对该节点的搜索次数。定位某节点的访问代价是为找到该节点而访问的节点总数。给定若干节点的标签及其访问频率，一棵最优二叉搜索树是由这些节点组成且期望访问代价最小的二叉搜索树。 你的任务是：给定一棵二叉搜索树，试着为每个节点指定访问频率，使得该二叉搜索树是唯一的最优二叉搜索树（即它的期望访问代价严格小于任何其他由相同节点、相同访问频率构成的二叉搜索树）。 原始问题的输入 输入包含一个测试用例。测试用例以整数 $N$ 开始（$1\le N\le50$），表示最优二叉搜索树中的节点数。为简化起见，节点标签为 $1$ 到 $N$。接下来的 $N$ 行描述树的结构。第 $i$ 行包含标签为 $i$ 的节点的左、右子节点标签（空子树用 $-1$ 表示）。你可以假定输入总是定义了一棵合法的二叉搜索树。 原始问题的输出 对于该测试用例，输出一行，包含按节点标签递增顺序给出的各节点访问频率。为避免浮点数精度问题，频率应写为非负整数且无前导零（表示节点的访问概率等于该频率除以所有频率之和）。确保不输出超过 $10^{15}$ 的整数。 原始问题的样例输入 3 -1 -1 1 3 -1 -1 原始问题的样例输出 1 1 1 原始问题的提示 注意样例中描述的树形结构为： 2 / \ 1 3

现在你将得到原始问题的输入以及程序员的输出，你的任务是判断程序员的输出是否正确。

输入

输入包含若干测试用例，每个测试用例分两部分。第一部分是原始问题的输入，用 #开始 输入# 和 #结束 输入# 包围。第二部分是程序员的输出，用 #开始 程序员输出# 和 #结束 程序员输出# 包围。一行 #结束# 表示输入结束。

你可以假定第一部分的所有数据均合法，但第二部分可能包含除 #结束 程序员输出# 以外的任意内容。合法的程序员输出恰包含 1 行；若输出行数非 1 行，则显然错误。程序员输出的每行长度不超过 2000 个字符。

输出

对于每个测试用例，若程序员输出正确，则输出 Accepted；否则输出 Wrong。在比较时只忽略空格和制表符（\t）。

输入数据 1

#开始 输入#
3
-1 -1
1 3
-1 -1
#结束 输入#
#开始 程序员输出#
1 1 1
#结束 程序员输出#
#开始 输入#
10
-1 2
-1 3
-1 4
-1 5
-1 6
-1 7
-1 8
-1 9
-1 10
-1 -1
#结束 输入#
#开始 程序员输出#
512 256 128 64 32 16 8 4 2 89798
#结束 程序员输出#
#结束#

输出数据 1

Accepted
Wrong

提示

如果在 Windows 版 GCC 中使用 scanf 和 printf 输入输出 64 位整数，请不要使用 %lld，而应使用 %I64d，这是 Windows 版 GCC 的一个 bug。

来源

北京 2005