Rede de Computadores

O professor da disciplina Fundamentos de Redes dividiu a turma em $N$ grupos, numerados de 1 a $N$. Cada grupo $i$ teria que rodar um experimento de uma rede de computadores, com as seguintes condições:

1. o grupo seria composto por $n_i$ alunos;
2. o experimento teria duração de uma hora;
3. a rede de teria de ser composta por, no mínimo, $n_i$ computadores conectados;
4. durante a execução de um experimento, uma rede de computadores conectados pode ser utilizada apenas por um único grupo.

A universidade possui $M$ computadores em rede disponíveis para os experimentos dos alunos, rotulados $1, 2, \ldots, M$. Dois computadores estão conectados se eles podem trocar mensagens diretamente, através de um cabo de rede ligado a ambos, ou indiretamente, através do auxílio de uma sequência de computadores $c_1, c_2, ..., c_k$ tal que existe um cabo unindo os computadores $c_i$ e $c_{i + 1}$, para todos valores $i\in [1, k - 1]$.

Dados o número de grupos $N$, o número de computadores $M$, as quantidades $n_i$ de elementos em cada grupo e os $C$ cabos de redes disponíveis, gere uma escala de grupos para uso do laboratório durante a primeira hora, de modo que o número de grupos presentes seja o maior possível.

Entrada

A primeira linha da entrada contém os valores dos inteiros $N$ e $M$ ($1\leq N\leq 2\times 10^3, 1\leq M\leq 2\times 10^5$), separados um espaço em branco.

A segunda linha contém $N$ inteiros positivos $n_i$ ($1\leq n_i\leq 100$), separados por espaços em branco.

A terceira linha contém o inteiro $C$ ($0 \leq C\leq \min\lbrace M(M - 1)/2, 3\times 10^5\rbrace$).

As $C$ linhas seguintes contém, cada uma, as informações sobre um cabo, na forma de um par de rótulos $c_j$ e $c_k$ ($1\leq c_j, c_k\leq M, j\neq k$), separados um espaço em branco, significando que há um cabo de rede unindo os computadores $c_j$ e $c_k$.

Saída

A primeira linha da saída deve ser o número máximo $G$ de grupos que podem trabalhar simultaneamente na primeira hora.

As $G$ linhas seguintes devem conter as informações do agendamento, na forma $g\ n\ c_{i1}\ c_{i2}\ \ldots\ c_{in}$, indicando que o grupo $g$ pode trabalhar com a rede conectada formada pelos $n$ computadores $c_{i1}$ $c_{i2}$ $\ldots$ $c_{in}$. Os computadores podem ser listados em qualquer ordem, com um espaço em branco separado dois rótulos consecutivos.

Se houver mais de um agendamento possível, imprima qualquer um deles.

Exemplo de entrada 1

3 3
1 1 1
0

Exemplo de saída 1

3
3 1 3
2 1 2
1 1 1

Explicação do exemplo 1: Cada grupo fica com um computador.

Exemplo de entrada 2

2 4
2 2
2
1 4
2 3

Exemplo de saída 2

2
2 2 2 3
1 2 1 4

Explicação do exemplo 2: Os dois grupos usam as duas redes conectadas.

Exemplo de entrada 3

2 4
2 2
2
1 4
2 1

Exemplo de saída 3

1
2 3 1 4 2

Explicação do exemplo 3: Há duas redes conectadas, com 1 e 3 computadores, respectivamente. Devido às restrições do problema, apenas um grupo pode trabalhar.

Exemplo de entrada 4

5 10
5 4 3 2 1
7
1 8
2 5
9 3
7 6
1 6
4 7
3 2

Exemplo de saída 4

3
1 5 1 8 6 7 4
2 4 2 5 3 9
5 1 10