Spoj 839 Optimal Marks

定义无向图中一条边的值为该边所连接的两个顶点的值的异或值，整个无向图的值为图中所有边的值之和。

给定一个包含 $n$ 个顶点、$m$ 条边的无向图。部分顶点的值已经确定，其余顶点的值可由你决定，但必须为非负整数。

你需要为所有未确定的顶点赋值，使无向图的值最小；在此基础上，还需要使图中所有顶点的值之和最小。

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示图的顶点数和边数。

接下来 $n$ 行，每行包含一个整数，依次表示编号为 $1$ 至 $n$ 的顶点的值。若该整数为负数，则表示对应顶点的值未确定，需要由你决定。输入值的绝对值不超过 $10^9$。

接下来 $m$ 行，每行包含两个整数 $a$ 和 $b$，表示编号为 $a$ 和 $b$ 的顶点之间存在一条无向边。

保证图中不存在重边和自环。

输出格式

第一行输出一个整数，表示无向图的最小值。

第二行输出一个整数，表示在无向图的值最小时，所有顶点的值之和的最小值。

样例输入

3 2
    2
    -1
    0
    1 2
    2 3

样例输出

2
2

样例解释

将编号为 $2$ 的顶点的值设为 $0$ 即可得到最优结果。

数据范围

• $n\le 500$；
• $m\le 2000$；
• 输入的顶点值的绝对值不超过 $10^9$。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

3 2
    2
    -1
    0
    1 2
    2 3

输出

2
2