Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

I. Oh It's XOR
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a graph with $$$n$$$ vertices and $$$m$$$ undirected, unweighted edges. ($$$2 \leq n \leq 10$$$^$$$3$$$, $$$1 \leq m \leq \frac{n \cdot (n - 1)}{2}$$$)

Vertices are numbered from $$$1$$$ to $$$n$$$, and vertex $$$i$$$ has value $$$v_i$$$. ($$$0 \leq v_i \lt 2$$$^$$$30$$$)

Output the maximum value of $$$v_{p_1}$$$ ^ $$$v_{p_2}$$$ ^ ... ^ $$$v_{p_k}$$$ where $$$p$$$ is a an array with distinct values ($$$1 \leq p_i \leq n$$$, $$$1 \leq k \leq n$$$), such that there is an edge between $$$p_i$$$ and $$$p_{i+1}$$$ for $$$1 \leq i \lt k$$$, and ^ denotes the bitwise XOR operator.

Input

The first line of input will consist of two integers $$$n$$$ and $$$m$$$. ($$$2 \leq n \leq 10$$$^$$$3$$$, $$$1 \leq m \leq \frac{n \cdot (n - 1)}{2}$$$)

The next line will contain $$$v_1 ... v_n$$$. ($$$0 \leq v_i \lt 2$$$^$$$30$$$)

The $$$i$$$th of the next $$$m$$$ lines will contain $$$a_i$$$ and $$$b_i$$$, denoting an edge between vertex $$$a_i$$$ and vertex $$$b_i$$$. ($$$1 \leq a_i, b_i, \leq n$$$, $$$a_i \neq b_i$$$, each edge is unique)

Output

Output the answer.

Example
Input
5 5
1 4 3 2 5
1 2
2 3
3 4
4 5
3 5
Output
7