1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# 2024
# Maciej Szeptuch

import sys

MOD = 1000000007

def simulate(state, edge, edges):
    visited = set()
    visited.add(state)
    result = 0
    que = [state]
    while que:
        result += 1
        state = que[-1]
        que.pop()
        for e in range(edges):
            if state[edge[e*2]-1] != state[edge[e*2+1]-1]:
                continue

            new_state = list(state)
            new_state[edge[e*2]-1] = new_state[edge[e*2+1]-1] = not new_state[edge[e*2]-1]
            new_state = tuple(new_state)
            if new_state in visited:
                continue

            visited.add(new_state)
            que.append(new_state)

    return result


if __name__ == "__main__":
    data = tuple(int(x) for x in sys.stdin.read().split())
    verts = data[0]
    edges = data[1]
    state = tuple(data[2:2+verts])
    edge = tuple(data[2+verts:2+verts+edges*2])

    result = simulate(state, edge, edges)
    print(result)