Colorful Components#13016

Colorful Components

2 seconds
512 megabytes
Very hard

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:

You must output the minimum possible number of singleton vertices and one corresponding spanning subgraph achieving this minimum.

Input

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.

Output

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.

Examples

Example

Loading
Loading

Note

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 .