← 返回题目列表

Codeforces · 1255/B

B. 冰箱储物柜

中文机器翻译题面 查看原题

Hanh 住在合租公寓里。有 $$$n$$$ 人(包括 Hanh)住在那里,每个人都有一个私人冰箱。

$$$n$$$ 冰箱由多条钢链固定。每条钢链连接两台不同的冰箱,并受数字锁保护。冰箱的主人知道与其连接的所有连锁店的密码。只有当连接到冰箱的所有链条都解锁时,冰箱才能打开。例如,如果一台冰箱根本没有连接链条,那么任何 $$$n$$$ 人都可以打开它。

例如,图中有$$$n=4$$$个人和$$$5$$$链条。第一个人知道两个链的密码:$$$1-4$$$ 和 $$$1-2$$$。冰箱 $$$1$$$ 可以由其主人($$$1$$$ 人)打开,两个人 $$$2$$$ 和 $$$4$$$(一起行动)也可以打开它。

这些冰箱的重量为 $$$a_1, a_2, \ldots, a_n$$$。要制作连接冰箱 $$$u$$$ 和 $$$v$$$ 的钢链,您必须支付 $$$a_u + a_v$$$ 美元。请注意,房东允许您创建连接同一对冰箱的多个链条。

Hanh 的公寓房东要求您精确制作 $$$m$$$ 钢链,以便所有冰箱都是私人的。冰箱是私人的,当且仅当住在公寓的 $$$n$$$ 人中,只有主人可以打开它(即没有其他人单独行动可以打开它)。换句话说,如果存在$$$j$$$ ($$$i \ne j$$$) 且$$$j$$$ 可以打开冰箱$$$i$$$,则冰箱$$$i$$$ 不是私有的。

例如,图中所有冰箱都是私人的。另一方面,如果有 $$$n=2$$$ 冰箱并且只有一条链(连接它们),那么两台冰箱都不是私有的(两台冰箱不仅可以由其所有者打开,还可以由另一个人打开)。

楼主当然是想尽量减少所有钢链的总成本来满足他的要求。确定是否存在任何方法可以精确地制作 $$$m$$$ 链,如果是,则输出使总成本最小化的任何解决方案。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$T$$$ ($$$1 \le T \le 10$$$)。然后是测试用例的描述。

每个测试用例的第一行包含两个整数 $$$n$$$, $$$m$$$ ($$$2 \le n \le 1000$$$, $$$1 \le m \le n$$$)——分别是 Hanh 公寓的居住人数和房东需要的钢链数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^4$$$) — 所有冰箱的重量。

输出

对于每个测试用例:

- 如果没有解决方案,则打印单个整数 $$$-1$$$。
- 否则,打印单个整数 $$$c$$$ — 最小总成本。接下来的 $$$m$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$),这意味着第 $$$i$$$ 条钢链连接冰箱 $$$u_i$$$ 和$$$v_i$$$。一对冰箱之间可以有任意数量的链条。

如果有多个答案,请打印其中一个。

示例

输入 #1

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

输出 #1

8
1 2
4 3
3 2
4 1
-1
12
3 2
1 2
3 1