Last Updated: 1 Sep, 2025

Post-War Reconstruction

Moderate
Asked in company
Goldman Sachs

Problem statement

There are 'N' kingdoms, numbered from 0 to N-1, connected by 'E' bidirectional roads. A war has broken out, and 'P' of these kingdoms have become hostile invaders.

To protect themselves, the remaining defending kingdoms destroy all roads connected to any of the 'P' invading kingdoms. This action may isolate groups of defending kingdoms from each other.

Your task is to determine the resulting groups of connected, defending kingdoms after the war. A group is a set of kingdoms where every kingdom in the group can reach every other kingdom in the same group through a path of roads that only passes through other defending kingdoms.


Input Format:
The first line of input contains an integer 'N', the number of kingdoms.
The second line contains an integer 'E', the number of roads.
The next 'E' lines each contain two space-separated integers, u and v, representing a road between kingdom u and v.
The next line contains an integer 'P', the number of invading kingdoms.
The last line contains 'P' space-separated integers, representing the numbers of the invading kingdoms.


Output Format:
Print the groups of surviving kingdoms, one group per line.
The kingdoms within each group must be sorted in ascending order.
The groups themselves must be printed in ascending order, based on the number of the first kingdom in each sorted group.
Each kingdom number in the output must be followed by a single space.


Note:
The graph is 0-indexed.