You are given an undirected simple graph G = (V, E) with |V| = n vertices and |E| = m edges. Each vertex v \in V has a color c_v, represented by an integer.
A spanning subgraph of is a graph G' = (V, E') with E' \subseteq E, i.e. it uses the same set of vertices but an arbitrary subset of the edges.
A connected component of a graph is called colorful if no two vertices in that component have the same color. In other words, for every color , there is at most one vertex of color in the component.
A vertex is called a singleton in a graph if it has degree (it is an isolated vertex, forming a component of size ).
Your task is to choose a subset of edges E' \subseteq E and construct a spanning subgraph G' = (V,E') such that:
Every connected component of G' is colorful.
The number of singleton vertices in G' is as small as possible.
You must output the minimum possible number of singleton vertices and one corresponding spanning subgraph achieving this minimum.
The first line contains two integers and – the number of vertices and edges in the graph.
The second line contains integers c_1, c_2, \dots, c_n, where c_i is the color of vertex .
Each of the next lines contains two integers and , denoting an undirected edge between vertices and .
1 \le n \le 5 \cdot 10^3,
1 \le m \le 5 \cdot 10^3,
1 \le c_i \le n,
the given graph does not contain multiple edges or self-loops.
On the first line, print a single integer – the minimum possible number of singleton vertices among all spanning subgraphs G' = (V,E') in which every connected component is colorful.
On the second line, print an integer – the number of edges in your chosen set E'.
Then print lines, each containing two integers and – the edges of E'.
Any spanning subgraph G' = (V,E') that satisfies the conditions and yields exactly singleton vertices will be accepted.
Example
In the example, one optimal solution is to choose edges and . Then there are two connected components: and . Each component contains two vertices of different colors, hence both components are colorful. Every vertex has degree at least , so there are singleton vertices, which is optimal.
The input graph in the example.
An optimal colorful spanning subgraph G' of .