是不是堆

二叉堆可以用一棵完全二叉树来实现，但完全二叉树不一定满足堆的性质。本题就请你判断一棵给定的完全二叉树是不是堆。

时间限制：1000

内存限制：65536

输入

输入在一行中给出两个正整数：m（≤ 100）是将要测试的完全二叉树的数量；n（1 < n ≤ 1000）是完全二叉树中的结点数。 随后 m 行，每行给出 n 个互不相同的键值（均在整型范围内），为完全二叉树的层序遍历序列。

输出

对输入的每棵完全二叉树，如果它是最大堆（大顶堆），就在一行中输出 `Max Heap`；如果是最小堆（小顶堆），则输出 `Min Heap`；如果根本不是堆，则输出 `Not Heap`。然后在下一行输出这棵树的后序遍历序列。同行数字间以 1 个空格分隔，行首尾不得有多余空格。

样例输入

3 8
98 72 86 60 65 12 23 50
8 38 25 58 52 82 70 60
10 28 15 12 34 9 8 56

样例输出

Max Heap
50 60 65 72 12 23 86 98
Min Heap
60 58 52 38 82 70 25 8
Not Heap
56 12 34 28 9 8 15 10

树的同构

给定两棵树  T1 和 T2。如果 T1 可以通过若干次左右孩子互换就变成 T2，则我们称两棵树是“同构”的。例如图1给出的两棵树就是同构的，因为我们把其中一棵树的结点A、B、G的左右孩子互换后，就得到另外一棵树。而图2就不是同构的。

图一

图二

现给定两棵树，请你判断它们是否是同构的。

时间限制：1000

内存限制：65536

输入

输入给出2棵二叉树的信息。对于每棵树，首先在一行中给出一个非负整数 n(≤ 10)，即该树的结点数（此时假设结点从 0 到 n -1 编号）；随后 n 行，第 i 行对应编号第 i 个结点，给出该结点中存储的 1 个英文大写字母、其左孩子结点的编号、右孩子结点的编号。如果孩子结点为空，则在相应位置上给出 “-”。给出的数据间用一个空格分隔。注意：题目保证每个结点中存储的字母是不同的。

输出

如果两棵树是同构的，输出“Yes”，否则输出“No”。

样例输入

样例#1（对应图1）：

8
A 1 2
B 3 4
C 5 -
D - -
E 6 -
G 7 -
F - -
H - -
8
G - 4
B 7 6
F - -
A 5 1
H - -
C 0 -
D - -
E 2 -

样例#2（对应图2）：

8
B 5 7
F - -
A 0 3
C 6 -
H - -
D - -
G 4 -
E 1 -
8
D 6 -
B 5 -
E - -
H - -
C 0 2
G - 3
F - -
A 1 4

样例输出

样例#1：

Yes

样例#2：

No

树的偏斜度

对于一棵二叉树，令 nL 表示仅有左孩子的结点的个数，令 nR 表示仅有右孩子的结点的个数。这棵树的“偏斜度”定义为 Ds = nL - nR。本题就请你计算任一棵给定二叉树的 Ds。

时间限制：1000

内存限制：65536

输入

输入在第一行给出正整数 n (≤ 103)，为二叉树中结点个数。随后两行先后给出这棵树的后序遍历和中序遍历序列，键值为 1 到 n 的整数。同行数字间以空格分隔。

输出

在一行中按以下格式输出树的偏斜度： Ds = nL - nR

样例输入

7
1 2 7 5 4 3 6
1 2 3 4 7 5 6

样例输出

2 = 3 - 1

网红点打卡攻略

一个旅游景点，如果被带火了的话，就被称为“网红点”。大家来网红点游玩，俗称“打卡”。在各个网红点打卡的快（省）乐（钱）方法称为“攻略”。你的任务就是从一大堆攻略中，找出那个能在每个网红点打卡仅一次、并且路上花费最少的攻略。

时间限制：1000

内存限制：65536

输入

首先第一行给出两个正整数：网红点的个数 N（1 < N ≤ 200）和网红点之间通路的条数 M。随后 M 行，每行给出有通路的两个网红点、以及这条路上的旅行花费（为正整数），格式为“网红点1 网红点2 费用”，其中网红点从 1 到 N 编号；同时也给出你家到某些网红点的花费，格式相同，其中你家的编号固定为 0。 再下一行给出一个正整数 K，是待检验的攻略的数量。随后 K 行，每行给出一条待检攻略，格式为： n V1 V2 … Vn 其中 n (≤ 200) 是攻略中的网红点数，Vi 是路径上的网红点编号。这里假设你从家里出发，从 V1 开始打卡，最后从 Vn 回家。

输出

在第一行输出满足要求的攻略的个数。 在第二行中，首先输出那个能在每个网红点打卡仅一次、并且路上花费最少的攻略的序号（从 1 开始），然后输出这个攻略的总路费，其间以一个空格分隔。如果这样的攻略不唯一，则输出序号最小的那个。 题目保证至少存在一个有效攻略，并且总路费不超过 109。

样例输入

6 13
0 5 2
6 2 2
6 0 1
3 4 2
1 5 2
2 5 1
3 1 1
4 1 2
1 6 1
6 3 2
1 2 1
4 5 3
2 0 2
7
6 5 1 4 3 6 2
6 5 2 1 6 3 4
8 6 2 1 6 3 4 5 2
3 2 1 5
6 6 1 3 4 5 2
7 6 2 1 3 4 5 2
6 5 2 1 4 3 6

样例输出

3
5 11

提示

样例说明： 第 2、3、4、6 条都不满足攻略的基本要求，即不能做到从家里出发，在每个网红点打卡仅一次，且能回到家里。所以满足条件的攻略有 3 条。 第 1 条攻略的总路费是：(0->5) 2 + (5->1) 2 + (1->4) 2 + (4->3) 2 + (3->6) 2 + (6->2) 2 + (2->0) 2 = 14； 第 5 条攻略的总路费同理可算得：1 + 1 + 1 + 2 + 3 + 1 + 2 = 11，是一条更省钱的攻略； 第 7 条攻略的总路费同理可算得：2 + 1 + 1 + 2 + 2 + 2 + 1 = 11，与第 5 条花费相同，但序号较大，所以不输出。