Traffic System Validation

In a city, intersections are controlled by traffic signals. Each intersection displays either a green light (denoted by 1) or a red light (denoted by 0). There are roads connecting some intersections. The traffic system is considered valid if no two directly connected intersections both display a green signal.

Formally, given $n$ intersections and $m$ connections, let $S = [S_1, S_2, \dots, S_n]$ be the list of signals where $S_i \in \{0,1\}$ represents the signal at the $i$th intersection. For each connection $(a, b)$, if both $S_a = 1$ and $S_b = 1$, then the traffic system is invalid. Otherwise, it is valid.

inputFormat

The input is provided via stdin and consists of multiple lines:

1. The first line contains two space-separated integers $n$ and $m$, where $n$ is the number of intersections and $m$ is the number of connections.
2. The second line contains $n$ space-separated integers (each either 0 or 1) representing the state of the traffic signals at the intersections.
3. Each of the following $m$ lines contains two space-separated integers $a$ and $b$, representing a direct road connecting intersections $a$ and $b$.

outputFormat

Output a single line to stdout containing either VALID if the traffic system is valid or INVALID if it is not.

3 2
1 0 1
1 2
2 3

VALID