#213842. [NWERC 2024] Binary Search

You are given an undirected graph with vertices and edges. Each vertex has a number written on it. This number is either or . A walk is a sequence of vertices in the graph such that any two consecutive vertices are connected by an edge. We call a binary sequence

walkable if there is a walk in the graph that satisfies .

In other words, a binary sequence is walkable if it is possible to obtain by walking in the graph and writing down the binary numbers in the order that they are visited. An example is visualized in Figure B.1.

:::align{center}

Figure B.1: Illustration of Sample Input 1. Every binary sequence of length at most 3 is walkable. :::

Your task is to find the length of a shortest binary sequence that is not walkable.

The input consists of:

• One line with two integers and (, ), the number of vertices and the number of edges.
• One line with integers ( for each ), where is the number written on vertex .
• lines, each with two integers and (, ), denoting that the vertices and are connected by an edge. It is guaranteed that every pair of vertices is connected by at most one edge.

If every binary sequence is walkable, output "". Otherwise, output the length of a shortest binary sequence that is not walkable.

样例输入 1

4 4
0 0 1 1
1 2
1 3
2 3
3 4

样例输出 1

4

样例输入 2

6 7
0 0 1 1 0 1
1 2
3 1
1 4
2 3
4 2
3 4
5 6

样例输出 2

infinity

样例输入 3

1 0
0

样例输出 3

1