题目描述

定义无向图中的一条边的值为：这条边连接的两个点的值的异或值。

定义一个无向图的值为：这个无向图所有边的值的和。

给你一个有 $n$ 个结点 $m$ 条边的无向图。其中的一些点的值是给定的，而其余的点的值由你决定（但要求均为非负数），使得这个无向图的值最小。在无向图的值最小的前提下，使得无向图中所有点的值的和最小。

输入格式

第一行，两个整数 $n$ 和 $m$ ，表示图的点数和边数。

接下来 $n$ 行，每行一个整数，按编号给出每个点的值。（若为负数则表示这个点的值由你决定，值的绝对值大小不超过 $10^9$ ）

接下来 $m$ 行，每行二个整数 $a,b$ ，表示编号为 $a$ 与 $b$ 的两点间连一条边。（保证无重边与自环）

输出格式

第一行，一个整数，表示无向图的值。

第二行，一个整数，表示无向图中所有点的值的和。

3 2
2
-1
0
1 2
2 3

2
2

样例说明 1

$2$ 结点的值定为 $0$ 即可。

数据规模与约定

对于 $100\%$ 的数据，$n\le 500 , m\le 2000$ ，保证图中无重边和自环。