Rating 1300

2146C 错误的二分查找

来源：Codeforces Round 1052 (Div. 2)-C. Wrong Binary Search

Tags: 二分查找 构造算法

给定一个整数 $n$ 和一个长度为 $n$ 的二进制字符串 $^{\text{∗}}$ $s$。

对于一个长度为 $n$ 的排列 $^{\text{†}}$ $p$ 和一个整数 $x$，我们按照以下伪代码定义 $\text{find}(x)$：

function find(int x):
    l := 1
    r := n
    while l <= r:
        let m be a random integer between l and r (inclusive)
        if p[m] == x
            return m
        if p[m] > x:
            r := m - 1
        else:
            l := m + 1
    return undefined     // 未找到

我们称整数 $x$ ($1\le x\le n$) 是稳定的，当且仅当无论在上述伪代码执行过程中如何选择 $m$ 的值，$\text{find}(x)$ 总是不会返回 undefined，并且 $p_{\text{find}(x)}=x$ 总是成立。

你需要构造一个长度为 $n$ 的排列 $p$，使得：

• 对于每个 $1\le i\le n$，整数 $i$ 是稳定的当且仅当 $s_i=\mathtt{1}$。

或者确定这样的排列不存在。

$^{\text{∗}}$ 二进制字符串是指每个字符都是 $\mathtt{0}$ 或 $\mathtt{1}$ 的字符串。

$^{\text{†}}$ 长度为 $n$ 的排列是一个由 $1$ 到 $n$ 的 $n$ 个不同整数按任意顺序组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（$2$ 在数组中出现两次），$[1,3,4]$ 也不是排列（$n=3$ 但数组中出现了 $4$）。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^4$)。接下来是测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ($2\le n \le 2\cdot 10^5$) —— 排列的长度。

第二行包含一个长度为 $n$ 的二进制字符串 $s$ ($s_i=\mathtt{0}$ 或 $\mathtt{1}$)。

保证所有测试用例的 $n$ 的总和不超过 $2\cdot 10^5$。

输出

对于每个测试用例：

• 如果这样的排列不存在，在输出的唯一一行打印 "NO"。
• 否则，在输出的第一行打印 "YES"。然后在第二行输出 $n$ 个不同的整数 $p_1, p_2, \ldots, p_n$ ($1\le p_i\le n$) —— 你构造的排列。

你可以以任意大小写形式输出标记。例如，字符串 "yEs"、"yes"、"Yes" 和 "YES" 将被识别为肯定响应。

如果有多个答案，你可以输出其中任意一个。

测试用例

输入

6
3
111
5
00000
5
10100
7
0010000
11
00001001100
12
011100010000

输出

YES
1 2 3 
YES
2 4 3 5 1
NO
YES
2 1 3 5 7 6 4
YES
2 1 4 3 5 7 6 8 9 11 10
NO

注意

在第一个测试用例中，我们构造了 $p=[1,2,3]$。以 $\text{find(2)}$ 为例：

• 初始时，$l=1$ 且 $r=3$；
• 我们将在 $l=1$ 到 $r=3$ 之间随机选择一个整数作为 $m$。
  • 如果我们选择 $m=1$：
    • $p_1=1< 2$，所以 $l$ 被设置为 $m + 1 = 2$。现在 $l=2$ 且 $r=3$；
    • 我们将在 $l=2$ 到 $r=3$ 之间随机选择一个整数作为 $m$。
    • 如果我们选择 $m=2$：$p_2=2$，所以返回值为 $2$。
    • 如果我们选择 $m=3$：$p_3=3>2$，所以 $r$ 被设置为 $m-1=2$。现在 $l=2$ 且 $r=2$，所以我们只能选择 $m=2$。$p_2=2$，所以返回值为 $2$。
  • 如果我们选择 $m=2$：
    • $p_2=2$，所以返回值为 $2$。
  • 如果我们选择 $m=3$，过程与选择 $m=1$ 时类似。返回值总是 $2$。
• 因此，无论在执行过程中如何选择 $m$，$\text{find}(2)$ 的返回值总是 $2$。

所以 $p_{\text{find}(2)}= p_2 = 2$ 总是成立，整数 $2$ 是稳定的。

类似地，我们可以证明整数 $1$ 和 $3$ 也是稳定的。因此，排列 $p = [1, 2, 3]$ 是一个有效的答案。

在第二个测试用例中，我们构造了 $p=[2,4,3,5,1]$。以 $\text{find(3)}$ 为例：

• 初始时，$l=1$ 且 $r=5$；
• 我们将在 $l=1$ 到 $r=5$ 之间随机选择一个整数作为 $m$。假设我们选择 $m=2$；
• $p_2=4>3$，所以 $r$ 被设置为 $m-1=1$。现在 $l=1$ 且 $r=1$；
• 我们将在 $l=1$ 到 $r=1$ 之间随机选择一个整数作为 $m$。我们只能选择 $m=1$；
• $p_1=2<3$，所以 $l$ 被设置为 $m + 1 = 2$。现在 $l=2$ 且 $r=1$；
• 由于 $l>r$，循环退出，返回值为 undefined。

因此，$\text{find}(3)$ 的返回值是 undefined，所以整数 $3$ 不是稳定的。

类似地，我们可以证明整数 $1$、$2$、$4$ 和 $5$ 也不是稳定的。因此，$p = [2, 4, 3, 5, 1]$ 是一个有效的答案。

其他一些排列，例如 $p=[5,4,3,2,1]$ 和 $p=[3,5,1,4,2]$，也是有效的答案。你可以输出其中任意一个。

在第三个测试用例中，可以证明这样的排列不存在。

2143C 最大树

来源：Codeforces Round 1051 (Div. 2)-C. Max Tree

Tags: 构造算法 深度优先搜索及其类似算法 图 贪心

给定一棵由 $n$ 个顶点组成的树，顶点编号从 $1$ 到 $n$。$n - 1$ 条边中的每条边都关联着两个非负整数 $x$ 和 $y$。

考虑一个 $1$ 到 $n$ 的整数的排列 $^{\text{∗}}$ $p$，其中 $p_i$ 表示分配给顶点 $i$ 的值。

对于一条边 $(u, v)$（满足 $u < v$）及其关联的值 $x$ 和 $y$，其贡献定义如下：

$$\begin{cases} x & \text{如果 } p_u > p_v, \\ y & \text{否则。} \end{cases}$$

该排列的价值是所有边的贡献之和。

你的任务是找到最大化这个总价值的任意一个排列 $p$。

$^{\text{∗}}$ 长度为 $n$ 的排列是一个由 $1$ 到 $n$ 的 $n$ 个不同整数按任意顺序组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（$2$ 在数组中出现两次），$[1,3,4]$ 也不是排列（$n=3$ 但数组中出现了 $4$）。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^4$)。接下来是测试用例的描述。

第一行包含一个整数 $n$ ($2 \le n \le 2 \cdot 10^5$) —— 树中顶点的数量。

接下来的 $n - 1$ 行，每行包含四个整数 $u$, $v$, $x$, $y$ ($1 \le u < v \le n$, $1 \le x, y \le 10^9$) —— 描述顶点 $u$ 和 $v$ 之间的一条边及其关联的值 $x$ 和 $y$。保证给定的边构成一棵树。

保证所有测试用例的 $n$ 的总和不超过 $2 \cdot 10^5$。

输出

对于每个测试用例，你必须输出一个 $1$ 到 $n$ 的整数的排列 $p$，该排列能最大化问题定义中的总价值。如果有多个答案，你可以输出其中任意一个。

测试用例

输入

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

输出

3 2 1 
2 3 5 4 1 
1 5 2 3 4 

注意

在第一个测试用例中：

考虑排列 $p = [3, 2, 1]$。其价值为 $5 = 2 + 3$。原因如下：

• 由于 $p_1 > p_2$，第一条边的贡献为 $+2$。
• 由于 $p_2 > p_3$，第二条边的贡献为 $+3$。

其他一些排列的价值如下：

• $p = [1, 2, 3]$ 的价值为 $1 + 2 = 3$。
• $p = [1, 3, 2]$ 的价值为 $1 + 3 = 4$。
• $p = [3, 1, 2]$ 的价值为 $2 + 2 = 4$。

在第二个测试用例中：

$p = [2, 3, 5, 4, 1]$ 的价值为 $3 + 2 + 7 + 100 = 112$。另一个可能的正确答案是 $p = [2, 3, 4, 5, 1]$。

2129A 双重视角

来源：Codeforces Round 1040 (Div. 1)-A. Double Perspective

Tags: 构造算法 动态规划 并查集 图 贪心 排序

对于一个由数对构成的集合 $S = \{(a_1, b_1), (a_2, b_2), \ldots, (a_m, b_m)\}$，其中对所有 $1 \le i \le m$ 有 $a_i < b_i$，我们定义 $f(S)$ 和 $g(S)$ 如下：

• 将每个 $(a_i, b_i)$ 视为数轴上的一个线段，$f(S)$ 是它们的并集的长度。形式化地说，$f(S)$ 是满足存在某个 $i$ ($1 \leq i \leq m$) 使得 $[x, x+1] \subseteq [a_i, b_i]$ 的整数 $x$ 的数量。

• 将每个 $(a_i, b_i)$ 视为一个无向图中的一条边，$g(S)$ 是位于至少一个包含至少 $3$ 条边的简单环上的节点数量。形式化地说，$g(S)$ 是满足在图中存在一条路径 $x_1 \to x_2 \to \ldots \to x_k \to x_1$ 的节点 $x_1$ 的数量，其中 $k \geq 3$ 且所有 $x_1, x_2, \ldots, x_k$ 互不相同。

例如，对于 $S = \{(1,2), (2,4), (1,4), (4,5),(6,7)\}$，我们可以得到 $f(S) = 5$ 和 $g(S) = 3$。

给定 $n$ 个互不相同的数对。你的任务是选择这些数对的一个子集 $S'$，使得 $f(S') - g(S')$ 最大化。你需要输出所选数对的索引。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^4$)。接下来是测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 3 \cdot 10^3$)。

接下来的 $n$ 行，每行包含两个整数 $a_i$ 和 $b_i$ ($1 \le a_i < b_i \le 2n$)，表示一个数对。

保证在同一测试用例中所有数对是互不相同的。

保证所有测试用例的 $n^2$ 的总和不超过 $9 \cdot 10^6$。

输出

对于每个测试用例，第一行包含一个整数 $k$ ($0 \le k \le n$) —— 子集 $S'$ 的大小。

第二行包含 $k$ 个整数 $i_1, i_2, \ldots, i_m$ ($1 \le i_1 , i_2 , \ldots , i_k \le n$) —— 所选数对的索引。注意索引必须是互不相同的。

测试用例

输入

2
1
1 2
4
1 2
2 3
1 3
3 5

输出

1
1
3
1 2 4

注意

在第一个测试用例中，如果不选择任何数对（即 $S'=\varnothing$），则 $f(S')-g(S')=0-0=0$。如果选择第一个数对，则 $f (S') - g (S')=1-0=1$。因此最优解是选择第一个数对。

2127B 哈米德？

来源：Atto Round 1 (Codeforces Round 1041, Div. 1 + Div. 2)-B. Hamiiid, Haaamid... Hamid?

Tags: 游戏 贪心

Mani 把 Hamid 关在一个 $1 \times n$ 的网格中。最初，网格中的一些单元格是墙，其余的是空的，Hamid 位于一个空单元格中。

每一天，按顺序发生以下事件：

1. Mani 选择一个空单元格并在该单元格建造一堵墙。注意，他不能在 Hamid 当前所在的单元格建造墙；
2. Hamid 选择一个方向（左或右），然后：
   • 如果该方向没有墙，他将逃离网格；
   • 否则，他将移动到该方向上最近的那堵墙并摧毁它。在这一天结束后，Hamid 位于被摧毁的墙的位置。

以下是 $n=6$ 时一个可能的行动序列示例：

Hamid 总是知道墙的位置。他希望最小化逃离网格所需的天数，而 Mani 希望最大化它。

你需要确定在双方都采取最优策略的情况下，Hamid 逃离网格所需的天数。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^4$)。接下来是测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $x$ ($2 \leq n \leq 2 \cdot 10^5$, $1 \leq x \leq n$) —— 分别是网格的大小和 Hamid 的初始位置。他最初位于从左到右第 $x$ 个单元格。

第二行包含一个长度为 $n$ 的字符串 $s$ ( $s_i=$"#" 或 $\texttt{"."}$ ) —— 网格的初始状态。如果 $s_i=$"#" ，则网格的第 $i$ 个单元格有一堵墙；如果 $s_i=\texttt{"."}$ ，则该单元格为空。

保证第 $x$ 个单元格是空的，并且网格中至少有两个空单元格。

保证所有测试用例的 $n$ 的总和不超过 $2 \cdot 10^5$。

输出

对于每个测试用例，输出一个整数 —— 在双方都采取最优策略的情况下，Hamid 逃离网格所需的天数。

测试用例

输入

4
3 1
..#
4 2
....
5 3
##..#
6 4
#...#.

输出

1
1
3
3

注意

在第一个测试用例中，Mani 必须在单元格 $2$ 建造一堵墙，因此 Hamid 可以在第一天从网格的左侧逃离。

在第二个测试用例中，如果 Mani 将墙建在 Hamid 的左边，Hamid 可以从右边逃离。如果墙建在 Hamid 的右边，他可以从左边逃离。因此，答案是 $1$。

在第三个测试用例中：

可以证明在上面的图示中双方都采取了最优策略。

在第四个测试用例中，我们在题目描述中展示了一个行动示例。注意，在这个示例中玩家没有采取最优策略。

2124C 子集乘法

来源：EPIC Institute of Technology Round Summer 2025 (Codeforces Round 1036, Div. 1 + Div. 2)-C. Subset Multiplication

Tags: 构造算法 贪心 数学 数论

Alice 有一个由 $n$ 个正整数组成的数组 $a$。该数组满足一个优美的性质：对于每个 $1 \leq i \leq n - 1$，$a_i$ 能整除 $a_{i+1}$。

Bob 看到 Alice 的优美数组后心生嫉妒。为了破坏它，Bob 首先创建一个大小为 $n$ 的数组 $b$，使得对每个 $1 \leq i \leq n$ 有 $b_i=a_i$。然后，他选择一个正整数 $x$，并将 $b$ 中的一些（可能没有，也可能是全部）元素乘以 $x$。

形式化地说，他选择一个（可能为空的）子集 $S\subseteq\{1,2,\ldots,n\}$，并对每个 $i\in S$，令 $b_i:=b_i\cdot x$。

你被给定数组 $b$，但你不知道数组 $a$ 和所选的数 $x$。请输出 Bob 可能选择的任意一个整数 $x$，使得将正确的数组 $a$ 的某个子集的元素乘以 $x$ 后能得到数组 $b$。保证答案存在。如果有多个可能的整数，你可以输出其中任意一个。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 2\cdot10^5$)。接下来是测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ($2 \leq n \leq 6\cdot10^5$) —— 数组 $b$ 的长度。

每个测试用例的第二行包含 $n$ 个整数 $b_1,b_2,\ldots,b_n$ ($1 \leq b_i \leq 10^9$) —— 表示数组 $b$。

保证数组 $b$ 可以按照题目描述的方式从某个优美数组 $a$ 和某个正整数 $x$ 得到。

保证所有测试用例的 $n$ 的总和不超过 $6\cdot 10^5$。

输出

对于每个测试用例，在新的一行输出任意一个可能的 $x$ 值 ($1 \leq x \leq 10^9$)。保证至少存在一个 $x$ 值。

测试用例

输入

4
2
2 4
3
1 1000000000 500000000
4
4 8 4 8
7
42 42 14 84 28 73080 255780

输出

343
2
4
6

注意

在第一个测试用例中，Bob 可能选择了 $x=343$ 和 $S=\{\}$（意味着他根本没有改变数组 $a$）。

在第三个测试用例中，Bob 可能选择了 $x=4$ 和 $S=\{1,2\}$，意味着他将 $b_1$ 和 $b_2$ 都乘以了 $4$。原始数组是 $\{1,2,4,8\}$，它满足所需的性质。

Rating 1400

2127C 旅行购物

来源：Atto Round 1 (Codeforces Round 1041, Div. 1 + Div. 2)-C. Trip Shopping

Tags: 游戏 贪心 排序

Ali 和 Bahamin 决定在伊朗美丽的南部海岸度过暑假。他们还同意在旅行期间进行购物——但他们没有设定固定预算，而是决定通过玩一个游戏来确定花费金额。

游戏在两个数组 $a$ 和 $b$ 上进行，每个数组包含 $n$ 个整数。

游戏将进行 $k$ 轮。在一轮中：

• 首先，Ali 选择两个索引 $i$ 和 $j$ ($1 \leq i < j \leq n$)；
• 然后，Bahamin 任意地重新排列四个整数 $a_i$, $a_j$, $b_i$, $b_j$。注意 Bahamin 可以在两个数组之间交换数字。他也可以保持两个数组不变。

在所有 $k$ 轮结束后，游戏的价值定义为 $v=\sum\limits_{i=1}^{n} |a_i-b_i|$。Ali 和 Bahamin 将在旅行中恰好花费 $v$ 枚硬币。

然而，他们的目标截然不同：

• Ali 希望尽可能少花费，即最小化 $v$；
• Bahamin 希望尽可能多花费，即最大化 $v$。

你需要找出在 Ali 和 Bahamin 都采取最优策略的情况下，他们最终将花费的硬币数量。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^4$)。接下来是测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $k$ ($2 \leq n \leq 2 \cdot 10^5$, $1 \leq k \leq n$) —— 分别是数组 $a$ 和 $b$ 的长度，以及游戏的轮数。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$ ($1 \leq a_i \leq 10^9$) —— 数组 $a$ 的元素。

第三行包含 $n$ 个整数 $b_1,b_2,\ldots,b_n$ ($1 \leq b_i \leq 10^9$) —— 数组 $b$ 的元素。

保证所有测试用例的 $n$ 的总和不超过 $2 \cdot 10^5$。

输出

对于每个测试用例，输出一个整数 —— 在 Ali 和 Bahamin 都采取最优策略的情况下，他们最终将花费的硬币数量。

测试用例

输入

5
2 1
1 7
3 5
3 2
1 5 3
6 2 4
5 4
1 16 10 10 16
3 2 2 15 15
4 1
23 1 18 4
19 2 10 3
10 10
4 3 2 100 4 1 2 4 5 5
1 200 4 5 6 1 10 2 3 4

输出

8
9
30
16
312

注意

在第一个测试用例中，Ali 只能选择 $(i, j) = (1, 2)$，而 Bahamin 可以重新排列所有四个数字。因此，他可以分配 $a = [5, 1]$ 和 $b = [3, 7]$。游戏的价值将为 $v=|5 - 3| + |1 - 7| = 8$。可以证明这是 Bahamin 能达到的最大可能值——其他排列如 $a = [5, 7],\space b = [1, 3]$ 也是可能的，但它们没有更大的值。

在第二个测试用例中，Bahamin 的最佳策略是无论 Ali 选择什么索引，都保持两个数组不变。游戏的价值将为 $v=|1 - 6| + |5 - 2| + |3 - 4| = 9$。

2123E MEX 计数

来源：Codeforces Round 1034 (Div. 3)-E. MEX Count

Tags: 二分查找 数据结构 贪心 排序 双指针

定义一个数组的 $\mathrm{MEX}$（最小排除值）为该数组中未出现的最小非负整数。例如：

• $\mathrm{MEX}([2, 2, 1]) = 0$，因为 $0$ 不在数组中。
• $\mathrm{MEX}([3, 1, 0, 1]) = 2$，因为 $0$ 和 $1$ 在数组中，但 $2$ 不在。
• $\mathrm{MEX}([0, 3, 1, 2]) = 4$，因为 $0$、$1$、$2$、$3$ 都在数组中，但 $4$ 不在。

给定一个大小为 $n$ 的非负整数数组 $a$。

对于所有 $k$ ($0\leq k \leq n$)，统计从 $a$ 中恰好移除 $k$ 个值后，$\mathrm{MEX}(a)$ 的可能取值数量。

输入

第一行包含一个整数 $t$ ($1\leq t\leq 10^4$) —— 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$ ($1\leq n\leq 2\cdot 10^5$) —— 数组 $a$ 的大小。

每个测试用例的第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$ ($0\leq a_i\leq n$)。

保证所有测试用例的 $n$ 的总和不超过 $2\cdot 10^5$。

输出

对于每个测试用例，输出一行包含 $n+1$ 个整数 —— 对于 $k=0,1,\dots,n$，在恰好移除 $k$ 个值后 $\mathrm{MEX}(a)$ 的可能取值数量。

测试用例

输入

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

输出

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

注意

在第一个样例中，考虑 $k=1$。如果移除一个 $0$，则得到以下数组：

因此得到 $\mathrm{MEX}(a) = 3$。或者，如果移除 $2$，则得到以下数组：

因此得到 $\mathrm{MEX}(a) = 2$。可以证明，在恰好移除一个值后，这些是 $\mathrm{MEX}(a)$ 唯一可能的值。因此 $k=1$ 的输出是 $2$。

2120C 神圣之树

来源：Codeforces Round 1033 (Div. 2) and CodeNite 2025-C. Divine Tree

Tags: 构造算法 贪心 数学 排序 树

Harshith 在一棵神圣之树下训练，在竞技编程中获得了启迪。神圣之树是一棵有根树 $^{\text{∗}}$，包含 $n$ 个节点，编号从 $1$ 到 $n$。节点 $v$ 的神圣性，记为 $d(v)$，定义为从根节点到节点 $v$ 的唯一简单路径上的最小节点编号。

Aryan 作为一名渴望知识的竞技程序员，请求 Harshith 传授知识。Harshith 同意了，但条件是给 Aryan 两个正整数 $n$ 和 $m$，他必须构造一棵包含 $n$ 个节点的神圣之树，使得树的总神圣性为 $m$，即 $\displaystyle\sum\limits_{i=1}^n d(i)=m$。如果不存在这样的树，Aryan 必须报告这是不可能的。

为了获得知识，Aryan 向你求助来完成这个任务。作为他的好朋友，请帮助他解决这个任务。

$^{\text{∗}}$ 树是一种无环连通图。有根树是指其中一个顶点特殊，称为根的树。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^4$)。接下来是测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 10^6$, $1 \le m \le 10^{12}$)。

保证所有测试用例的 $n$ 的总和不超过 $10^6$。

输出

对于每个测试用例，在一行中输出一个整数 $k$ —— 树的根节点。

然后输出 $n-1$ 行，每行描述树的一条边 —— 一对正整数 $u_i,v_i$ ($1\le u_i,v_i\le n$, $u_i\ne v_i$)，表示第 $i$ 条边连接顶点 $u_i$ 和 $v_i$。

边和边的顶点可以以任意顺序输出。如果有多个解决方案，输出其中任意一个。

如果没有解决方案，则输出 "-1"。

测试用例

输入

2
1 2
4 6

输出

-1
3
3 1
1 2
2 4

注意

在第一个测试用例中，只有一个节点，其值为 $1$，因此无法得到总和 $2$。

在第二个测试用例中，使用给定的以 $3$ 为根的树，可以得到总和 $6$。

2114E 绮礼袭击庄园

来源：Codeforces Round 1027 (Div. 3)-E. Kirei Attacks the Estate

Tags: 深度优先搜索及其类似算法 动态规划 贪心 树

有一次，绮礼悄悄潜入了充满陷阱的爱因兹贝伦家庄园，但被切嗣的使魔发现。评估了自身实力后，绮礼决定撤退。庄园被表示为一棵有 $n$ 个顶点的树，根节点为顶点 $1$。树的每个顶点记录有一个数字 $a_i$，表示顶点 $i$ 的危险程度。回忆一下，树是一种无环的连通无向图。

为了成功撤退，绮礼必须计算每个顶点的威胁值。一个顶点的威胁值等于从该顶点开始的垂直路径上的最大交错和。从顶点 $i$ 开始的垂直路径的交错和定义为 $a_i - a_{p_i} + a_{p_{p_i}} - \ldots$，其中 $p_i$ 是顶点 $i$ 在通往根节点（顶点 $1$）的路径上的父节点。

例如，在下方的树中，顶点 $4$ 有以下垂直路径：

• $[4]$，交错和为 $a_4 = 6$；
• $[4, 3]$，交错和为 $a_4 - a_3 = 6 - 2 = 4$；
• $[4, 3, 2]$，交错和为 $a_4 - a_3 + a_2 = 6 - 2 + 5 = 9$；
• $[4, 3, 2, 1]$，交错和为 $a_4 - a_3 + a_2 - a_1 = 6 - 2 + 5 - 4 = 5$。

顶点的危险程度用红色标出。

帮助绮礼计算所有顶点的威胁值并逃离庄园。

输入

第一行包含一个整数 $t$ ($1 \le t \le 10^4$) —— 测试用例的数量。

接下来描述测试用例。

第一行包含一个整数 $n$ ($2 \le n \le 2 \cdot 10^5$) —— 树中顶点的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) —— 顶点的危险程度。

接下来的 $n - 1$ 行包含数字 $v, u$ ($1 \le v, u \le n$, $v \neq u$) —— 描述树的边。

保证所有测试用例的 $n$ 的总和不超过 $2 \cdot 10^5$。同时保证给定的边集构成一棵树。

输出

对于每个测试用例，输出 $n$ 个整数 —— 每个顶点的威胁值。

测试用例

输入

2
5
4 5 2 6 7
1 2
3 2
4 3
5 1
6
1000000000 500500500 900900900 9 404 800800800
3 4
5 1
2 5
1 6
6 4

输出

4 5 2 9 7 
1000000000 1500500096 1701701691 199199209 404 800800800 

注意

第一个测试用例中的树在题目描述中已给出，最大变号和的实现如下：

1. $a_1 = 4$；
2. $a_2 = 5$；
3. $a_3 = 2$；
4. $a_4 - a_3 + a_2 = 6 - 2 + 5 = 9$；
5. $a_5 = 7$。

2111D 创建课程表

来源：Educational Codeforces Round 179 (Rated for Div. 2)-D. Creating a Schedule

Tags: 构造算法 数据结构 贪心 实现 排序

新学期即将开始，需要为第一天制定课程表。学院总共有 $n$ 个班级和 $m$ 间教室。已知每个班级在第一天恰好有 $6$ 节课，且每个班级的第 $k$ 节课在同一时间进行。每节课必须在教室中进行，并且同一时间同一教室不能有超过一个班级上课。

每间教室都有自己的编号（至少三位数），该编号除最后两位外的所有数字表示教室所在的楼层。例如，教室 $479$ 位于第 $4$ 层，而教室 $31415$ 位于第 $314$ 层。楼层之间可以通过楼梯移动；对于任何楼层 $x > 1$，可以下到 $x - 1$ 层或上到 $x + 1$ 层；从第一层只能上到第二层；从第 $10^7$ 层（最后一层）只能下到第 $9999999$ 层。

学院教务处决定以这样的方式制定课程表：使得学生在楼层之间的移动尽可能多，即所有班级在楼层之间的移动总次数应最大化。当学生从一层移动到另一层时，他们走最短路径。

例如，如果有 $n = 2$ 个班级和 $m = 4$ 间教室 $[479, 290, 478, 293]$，课程表可以安排如下：

课程序号	班级 1	班级 2
$1$	$290$	$293$
$2$	$478$	$479$
$3$	$293$	$290$
$4$	$479$	$478$
$5$	$293$	$290$
$6$	$479$	$478$

在这样的安排下，班级每次将在第 $2$ 层和第 $4$ 层之间移动，总共产生 $20$ 次楼层间移动。

请帮助教务处创建任意一个合适的课程表！

输入

每个测试包含多个测试用例。第一行包含一个整数 $t$ ($1 \le t \le 10^{3}$) —— 测试用例的数量。接下来是测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le m \le 10^{5}$) —— 分别是班级的数量和可用教室的数量。

每个测试用例的第二行包含 $m$ 个整数 $a_{i}$ ($100 \le a_{i} < 10^{9}$) —— 可用教室的编号。

输入附加约束：

• 所有教室编号互不相同；
• 所有测试用例的 $m$ 的总和不超过 $10^{5}$。

输出

对于每个测试用例，输出 $n$ 行，其中第 $i$ 行应包含 $6$ 个整数 —— 第 $i$ 个班级上课的教室编号。

在第 $k$ 节课时，每间教室最多只能被一个班级使用。

测试用例

输入

3
2 4
479 290 478 293
1 1
31415
6 10
479 385 290 293 384 383 297 478 291 382

输出

290 478 293 479 293 479
293 479 290 478 290 478
31415 31415 31415 31415 31415 31415
479 290 479 290 479 290
290 479 290 479 290 479
293 478 293 478 293 478
297 385 297 385 297 385
478 293 478 293 478 293
291 384 291 384 291 384

注意

在第三个测试用例中，教室之间的最大移动次数为 $50$。