O arquivo de entrada consiste de varios conjuntos de dados. Cada conjunto começa com o numero "x" de vertices de um grafo. A próxima linha contém dois inteiros representando o vértice s (sink) e t (target). As próximas "x" linhas contém as listas de adjacências do grafo, contendo a respectiva capacidade de cada aresta. O primeiro numero de cada uma das "x" linhas é um inteiro n tal que 1 <= n <= x. Depois seguem-se vários pares de inteiros v e c representando, onde v é um vértice adjacente ao vertice n e c é a capacidade da aresta correspondente. A lista de vertices adjacentes termina com o inteiro 0.
O arquivo de entrada é terminado por um conjunto de dados comecando com "x = 0". Esse conjunto não deve ser processado.

Considere que 0 <= x <= 100.

Entrada exemplo:
8
1 8
1 2 5 3 7 4 6 0
2 5 4 6 3 0
3 6 4 7 1 0
4 7 5 0
5 8 3 0
6 8 7 0
7 8 6 6 4 0
8 0
4
1 4
1 2 5 3 2 0
2 4 2 0
3 4 5 0
4 0
0

Arquivo de Saida: quest1.out

Para cada conjunto, voce deve imprimir x linhas, onde x é o número de vértices do grafo. Em cada uma das X linhas, imprima o  vértice do grafo e uma lista de pares de valores correspondendo à aresta e ao fluxo que está sendo passado por esta aresta. Por exemplo: 1 2 5, significa que a aresta que liga o vértice 1 ao 2 possui um fluxo de 5. Um linha em branco separa cada conjunto.

Saida exemplo correspondente a entrada acima:
Conjunto #1
1 2 5 3 5 4 5
2 5 3 6 2
3 6 4 7 1
4 7 5
5 8 3
6 8 7
7 6 1 8 5
8

Conjunto #2
1 2 2 3 2
2 4 2
3 4 2
4
 

Obs.:
 
 

• Não se esqueçam de desalocar toda a lista de adjacência do grafo entre cada processamento;
• O primeiro conjunto de dados do exemplo acima encontra-se explicado ,com ilustrações, no Udi Manber pg.240;
• Os vértices serão dados em ordem crescente e começando do número 1;
• O formato dos arquivos de saída deverá seguir EXATAMENTE o padrão estabelecido nos exemplos acima.

Arquivo de entrada: quest2.in

O arquivo de entrada consiste de varios conjuntos de dados. Cada conjunto comeca com uma linha contendo o numero "x" de vertices de um grafo. As proximas "x" linhas contem as listas de adjacencias do grafo que devem ser processadas. Os números seguintes representam os vértices  v adjacentes ao vértice n. Um conjunto em que x=0 indica o final do arquivo. Esse conjunto nao deve ser processado.

Considere que 0 <= x <= 100.

Entrada exemplo:

16
1 2 8 13 14 16 0
2 1 3 8 7 5 0
3 2 4 5 6 7 0
4 3 5 6 0
5 4 3 2 0
6 4 3 0
7 3 2 0
8 2 9 1 0
9 8 10 11 12 0
10 9 11 12 0
11 10 9 0
12 10 9 0
13 1 14 0
14 13 15 16 1 0
15 14 0
16 14 1 0
0

Arquivo de Saida: quest2.out

Para cada conjunto, voce deve imprimir "2*n+1" linhas, em que n e' o numero de componentes biconexos do grafo correspondente ao conjunto. A primeira linha contém o número do conjunto, as próximas 2*n linhas conterão o número do componente e logo em seguida os vértices pertencentes a cada subgrafo induzido pelo componente biconexo em ordem crescente.
Uma linha em branco separa cada conjunto.

Saida exemplo:

Conjunto #1
Componente 1:
2 3 4 5 6 7
Componente 2:
9 10 11 12
Componente 3:
8 9
Componente 4:
14 15
Componente 5:
1 13 14 16
Componente 6:
1 2 8
 

Obs.:

• Não se esqueçam de desalocar toda a lista de adjacência do grafo entre cada processamento;
• As listas de adjacências devem ser montadas na ordem dada, e os componentes devem ser impressos assim que forem identificados.
• Esta entrada exemplo encontra-se detalhada com ilustrações no livro de Udi Mamber, p.207.

• O formato dos arquivos de saída deverá seguir EXATAMENTE o padrão estabelecido nos exemplos acima.



---