题目描述

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

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

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

输入格式

第一行，两个数$\red{n，}$$\red{m，}$表示图的点数和边数。

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

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

输出格式

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

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

样例

输入样例

3 2
2
-1
0
1 2
2 3

输出样例

2
2

提示

数据约定 $\red{n<=500，}$$\red{m<=2000}$

样例解释 $\red{2}$结点的值定为$\red{0}$即可。

由于$\red{hzwer}$十分善良… 如果你的输出只有第一行正确，那么得$\red{5}$分 全部正确则满分