$D$-平衡树（$D$ 为正整数）是一棵满足以下条件的树： 每个节点要么是黑色，要么是白色。 对于每个黑色节点，至少存在另一个距离不超过 $D$ 的黑色节点。 * 对于每个白色节点，至少存在另一个距离不超过 $D$ 的白色节点。

给定一棵树，其中部分节点的颜色尚未确定。你需要为所有剩余的节点选择颜色，以最小化 $D$ 的值。然而，可能不存在合法的正整数 $D$ 使得该树是 $D$-平衡的（见样例）。

只有当你找到一个导致你所给答案的合法染色方案时，才能获得满分。否则可能会获得部分分。本题需要解决多棵树的问题。

输入格式

标准输入的第一行包含一个正整数 $T$，表示测试用例的数量。每个测试用例描述一棵树，包含： 第一行包含一个整数 $N$，表示树中的节点数。 接下来的 $(N-1)$ 行，每行包含一对 $(x, y)$，表示 $x$ 和 $y$ 之间的一条边。 * 最后一行包含 $N$ 个值 $c_i$，表示每个节点的颜色。

根据 $c_i$，节点的颜色可以是： 如果 $c_i$ 等于 $0$，则为白色。 如果 $c_i$ 等于 $1$，则为黑色。 * 如果 $c_i$ 等于 $-1$，则为白色或黑色（你需要自行选择）。

输出格式

输出应包含每个测试用例的答案，每行一个。每个答案的结构如下： 第一行，打印使得树成为 $D$-平衡的最小 $D$ 值。如果不存在这样的 $D$，则打印 -1（不带引号），并跳过下一行。 第二行，如果存在合法的正整数 $D$，则打印一个导致该答案的节点染色方案。如果未满足任何初始限制（通过覆盖固定颜色），则答案将被视为错误。然而，如果提供的染色方案没有导致所打印的 $D$，你仍可能获得部分分（见评分标准）。

数据范围

• 两个节点 $A$ 和 $B$ 之间的距离等于从 $A$ 到 $B$ 的唯一路径上的边数。
• $3 \le N \le 500\,000$
• 所有测试用例中 $N$ 的总和不超过 $500\,000$。
• 每个子任务可能根据“评分标准”部分获得满分或部分分。
• 节点从 $1$ 开始编号（即 $1, 2, 3, \dots, N$）。

评分标准

• 如果提供的染色方案与你的答案不一致，但满足所有初始条件，你将获得每个子任务 60% 的分数。
• 子任务的得分为该子任务中各测试点的最低得分。
• 请注意，第 4 个子任务可以获得四种不同的分数（0 分除外）：
  • $100\%$：如果 $Q = D$ 且染色方案与答案一致。
  • $60\%$：如果 $Q = D$ 且染色方案与答案不一致。
  • $50\%$：如果 $Q < D < Q + 4$ 且染色方案与答案一致。
  • $30\%$：如果 $Q < D < Q + 4$ 且染色方案与答案不一致。

样例

输入 1

3
3
1 2
2 3
0 0 -1
4
1 2
2 3
2 4
0 1 0 0
6
1 2
2 3
2 4
4 5
4 6
1 0 0 -1 1 0

输出 1

1
0 0 0
-1
2
1 0 0 1 1 0

Figure 1. 样例 1 中的树结构