URI Online Judge | 3101

Polygamous Families

By Ygor Ribeiro, IFSULDEMINAS BR Brazil

Timelimit: 1

In Namekusei polygamy is allowed, so it is very likely that a random Namekuseijin is somehow from the same family as any other. Two Namekuseijins are considered to be from the same family if there is a direct or indirect relationship of kinship between them, for example: Namekuseijin 1 is related to 2, 2 is related to 3 and 4, 4 is related to 5. We can see that 1 is related direct of 2, and 1 is an indirect relative of 3, 4 and 5. That is, all of these 5 are from the same family, since there are direct and indirect kinship relations between them.

It is easy to see that on this planet there are few different families, like the previous example, all 5 Namekuseijins are of only 1 family, but if there were still 4 other Namekuseijins, with the following kinship relations: 6 is related to 7, 8 is related of 9. With that, we will have 2 more different families and a total of 3 different families with all 9 inhabitants of that planet.

Can you help them by saying the count of families and what is the number of inhabitants in each?

Namekusei is going through a difficult time, Freezer is coming and intends to decimate the entire population if they do not deliver the dragon balls. A Namekuseijin would rather die than count where they are, so several inhabitants of Namekusei are dying and the count of families and inhabitants of each family is decreasing. As soon as Freezer was defeated by the warrior Goku, it was not known for sure how many different families still existed and what size each, that is, how many are part of it. Dendê was responsible for informing which of his countrymen died, but he is very nervous and can sometimes inform a Namekuseijin already said.

Input

You will be given two integers, N (1 <= N <= 500) and M (1 <= M <= 1000), which represent the number of inhabitants of the planet and the number of existing kinship relationships, respectively. Each of the following M lines contains two integers A and B (1 <= A, B <= N), representing the direct relationship relationships between A and B. Then you will be given an integer X (0 <= X < N), which represents the number of inhabitants that Dendê noted that they died. Each of the following X lines will have an integer Y (1 <= Y <= N), which represents that Namekuseijin Y died.

Output

You should show "Quantidade de familias: ", without quotes, followed by the number of families that still exist on the planet and show "Numero de habitantes em cada: ", without quotes, followed by the number of inhabitants that are part of each family. The quantity must be reported in ascending order. Follow the output example. NOTE: A family only exists if at least 1 inhabitant of the planet is part of it.

Input Samples Output Samples

9 6

1 2

2 3

2 4

4 5

6 7

8 9

2

1

8

Quantidade de familias: 3

Numero de habitantes em cada: 1, 2 e 4

9 6

1 2

2 3

2 4

4 5

6 7

8 9

2

8

9

Quantidade de familias: 2

Numero de habitantes em cada: 2 e 5