Classificando Componentes Conexos

#84
Made by: Crazynds
200MB
0.5s

Você recebeu um grafo não direcionado com $N$ vértices numerados de $1$ a $N$ e $M$ arestas. Esse grafo pode estar desconectado, ou seja, pode conter diversos componentes conexos.

Sua tarefa é identificar cada componente conexo e classificá-lo em exatamente uma das seguintes categorias:

  1. Árvore Binária: Um componente conexo é uma árvore binária se e somente se:

    • É uma árvore (ou seja, conexo e sem ciclos),
    • Cada nó possui grau no máximo 3, ou seja, pode ter no máximo dois "filhos" e um "pai".

  2. Árvore: Um componente conexo é uma árvore se for conexo e não contiver ciclos, mas não satisfizer as restrições de árvore binária (por exemplo, algum nó possui grau maior que 3).

  3. Grafo: Qualquer outro componente conexo que contenha pelo menos um ciclo.

Importante: Como toda árvore binária também é uma árvore, e toda árvore é um grafo, você deve classificar cada componente pela estrutura mais específica possível. Ou seja, se um componente for uma árvore binária, ele não deve ser listado como árvore ou grafo. Se for uma árvore que não é binária, deve ser listado como Árvore, e não como Grafo.

Sua saída deve listar todas as estruturas identificadas, em três blocos separados, na seguinte ordem:

  • Primeiro, todas as Árvores Binárias;
  • Em seguida, todas as Árvores;
  • Por fim, os Grafos.

Dentro de cada bloco, os componentes devem ser listados em ordem crescente pelo número de nós.

A saída deve ter o seguinte formato:

1-Arvore Binária: X
2-Arvore Binária: Y
3-Arvore: Z
4-Grafo: W
...

Ou seja, cada linha começa com a posição sequencial geral, seguida da categoria e da quantidade de nós daquele componente.

Input

A primeira linha contém dois inteiros $N$ e $M$ $(10 \leq N \leq 2.10^5, 10 \leq M \leq 2.10^5)$ — o número de vértices e o número de arestas.

As próximas $M$ linhas contêm dois inteiros $u$ e $v$ ($1 \leq u, v \leq N$, $u \neq v$) — indicando uma aresta entre os vértices $u$ e $v$.

Output

Imprima uma linha para cada componente conexo, no formato especificado, seguindo a ordem:

  1. Árvores Binárias (em ordem crescente de tamanho),
  2. Árvores (em ordem crescente de tamanho),
  3. Grafos (em ordem crescente de tamanho).

A numeração das estruturas deve iniciar em 1 e ser contínua.

Input Example
Output Example 
19 17
1 4
1 11
1 18
2 9
3 14
3 16
4 9
5 11
6 7
6 10
6 12
6 13
6 19
8 16
9 17
14 16
15 16

1-Arvore Binária: 8
2-Arvore: 6
3-Grafo: 5

13 11
1 3
2 11
3 5
4 11
5 7
5 8
6 11
9 10
9 11
11 13
12 13

1-Arvore Binária: 5
2-Arvore: 8

32 28
1 7
2 21
2 29
3 19
4 6
4 23
5 14
5 24
6 11
6 22
7 20
8 14
9 14
10 23
11 30
12 19
13 32
14 24
15 23
16 18
16 28
17 29
19 31
20 32
25 29
26 32
27 28
28 31

1-Arvore Binária: 5
2-Arvore Binária: 6
3-Arvore Binária: 8
4-Arvore Binária: 8
5-Grafo: 5