Diverse Shortest Path

You are given an undirected graph with n vertices and m edges. Each vertex is assigned an integer color. Your task is to determine if there exists any pair of vertices such that the shortest path between them passes through vertices of at least two distinct colors.

In other words, if there is any edge connecting two vertices with different colors, then the answer is "YES"; otherwise, if all adjacent vertices on every possible path share the same color, the answer is "NO".

Note: The vertices are numbered from 1 to n.

The mathematical condition can be expressed as: find an edge \( (u,v) \) such that \( c_u \neq c_v \), where \( c_i \) represents the color of vertex \( i \).

inputFormat

The first line of input contains two integers n and m, representing the number of vertices and edges, respectively.

The second line contains n space-separated integers representing the colors of the vertices (colors[1] to colors[n]).

Then follow m lines, each containing two space-separated integers u and v, representing an undirected edge between vertex u and vertex v.

outputFormat

Output a single line containing either "YES" if there exists at least one shortest path that includes vertices of two distinct colors, or "NO" otherwise.

5 4
1 2 1 2 3
1 2
2 3
3 4
4 5

YES