配点 : 100 点
問題文
长度 N-1 中广泛单调递增的正整数序列 X=(X_1,X_2,\dots,X_{N-1}) 。
N 頂点 M 简单边连通无向图 G 的成本 将其定义为 \sum_{i=1}^{N} \sum_{j=i+1}^{N} X_{d(i,j)} 。然而,d(i,j) 满足 G 顶点打开 i 到顶点 定义为移动到 j 之前可能通过的最小边数。
成本最小化 请拼搭 N 頂点 M 简单边连通无向图 G 输出为 1 块。
制約
- 2 \le N \le 100
- N-1 \le M \le \frac{N(N-1)}{2}
- 1 \le X_1 \le X_2 \le \dots \le X_{N-1} \le 10^9
入力
输入将以以下形式从标准输入给出。
N M
X_1 X_2 \dots X_{N-1}
出力
图中 i 真正的边是顶点 A_i 和顶点 连接 B_i 时,如下 M 行。
A_1 B_1 A_2 B_2 \vdots A_M B_M
入力例 1
3 2 4 5
出力例 1
1 2 1 3
对于此输出,成本为 X_{d(1,2)} + X_{d(1,3)} + X_{d(2,3)} = X_1 + X_1 + X_2 = 13 。
成本是 12 变得小于或等于 3 頂点 2 此输出是正确的,因为没有无向图。
入力例 2
4 6 12 34 56
出力例 2
1 2 1 3 1 4 2 3 2 4 3 4