#2001. graph

graph

题目描述

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

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

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

输入格式

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

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

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

输出格式

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

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

样例

输入样例

3 2
2
-1
0
1 2
2 3

输出样例

2
2

提示

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

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

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