Problema D



Determinização de Autómatos



Considere um autómato A não determinista sem transições є. Mais formalmente, sejam Σ um alfabeto, S um conjunto de estados, S0 e F dois subconjunto de S de estados (respectivamente conjunto de estados iniciais e conjunto de estados finais) e Rδ uma relação de transição sobre Σ e S. Temos assim A = Σ, S, S0 , F, Rδ.

Problem

Escreva um programa que lê A e que calcule um autómato A′ determinista equivalente a A.

Input

Para simplificar o formatos dos dados em entrada admitiremos aqui que o conjunto S é sempre da forma {1… n} (n inteiro), Σ é o alfabeto português. Assim A = {Σ, S, S0, F, Rδ} pode ser introduzido por:

Output

A descrição do autómato resultante, seguindo exactamente o formato de entrada.

Como o conjunto dos estados do autómato calculado poderá distanciar-se significativamente do conjunto de estado de A, tenha em atenção à necessidade em renomear os estados para que esses formam um conjunto da forma {1..m}.

A lista dos estados de entrada, dos estados finais e das transições é ordenada pela ordem lexicográfica usual.

Constraints

Não há limites particulares por definir. Os testes são todos de tamanho razoável...

Sample Input

3
2
1 2
2
2 3
5
1 a 1
1 b 2
2 a 2
2 a 3
3 b 3

Sample Output

5
1
1
5
1 2 3 4 5
8
1 a 2
1 b 3
2 a 2
2 b 4
3 a 4
4 a 4
4 b 5
5 b 5

This document was translated from LATEX by HEVEA.