Colorful Components

Обмеження: 2 сек., 512 МіБ

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 \(G\) 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 \(\gamma\), there is at most one vertex of color \(\gamma\) in the component.

A vertex is called a singleton in a graph if it has degree \(0\) (it is an isolated vertex, forming a component of size \(1\)).

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 \(n\) and \(m\) – the number of vertices and edges in the graph.

The second line contains \(n\) integers \(c_1, c_2, \dots, c_n\), where \(c_i\) is the color of vertex \(i\).

Each of the next \(m\) lines contains two integers \(u\) and \(v\), denoting an undirected edge between vertices \(u\) and \(v\).

Вихідні дані

On the first line, print a single integer \(s\) – 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 \(k\) – the number of edges in your chosen set \(E'\).

Then print \(k\) lines, each containing two integers \(u\) and \(v\) – the edges of \(E'\).

Any spanning subgraph \(G' = (V,E')\) that satisfies the conditions and yields exactly \(s\) singleton vertices will be accepted.

Обмеження

\(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.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 4 1 1 2 2 1 3 1 4 2 3 2 4	0 2 1 3 2 4

Примітки

In the example, one optimal solution is to choose edges \((1,3)\) and \((2,4)\). Then there are two connected components: \(\{1,3\}\) and \(\{2,4\}\). Each component contains two vertices of different colors, hence both components are colorful. Every vertex has degree at least \(1\), so there are \(0\) singleton vertices, which is optimal.