Seven Kingdoms#6397
Jon Dayne is the ruler of a vast country called the Seven Kingdoms. He has two sisters, Arya and Sansa, and he wishes to give them some of the cities of the Seven Kingdoms. He will govern the remaining cities, or, if none remain, he will go to the Wall—a colossal fortification along the northern border of the Seven Kingdoms—where he will become the Lord Commander. Arya is the Lady of Winterfell, and Sansa is the Lady of King's Landing. The cities in the Seven Kingdoms (including Winterfell and King's Landing) are connected by a network of roads (though some cities may be disconnected from others, either because they are on islands or because they are currently at war). There is no direct road between Winterfell and King's Landing, and they do not share any common neighboring city.
Jon wants to assign to each sister a set of cities such that, within each set, every pair of cities is joined by a direct road, and all remaining cities not in these two sets are also mutually connected by direct roads. The set assigned to Arya must include Winterfell, and the set assigned to Sansa must include King's Landing. Jon needs your help to determine whether such a partition is possible, and if so, to specify the cities in each set.
The input consists of a single test case. The first line contains two integers and , where 2 \leq n \leq 2000 is the number of cities, and is the number of roads. Each of the next lines contains two integers x_i and y_i (1 \leq x_i, y_i \leq n), representing a road connecting distinct cities x_i and y_i. Winterfell is city , and King's Landing is city in this network.
If it is not possible to partition the cities as required, output impossible. Otherwise, output two lines: the first line should contain the list of cities assigned to Arya, and the second line the list assigned to Sansa. If multiple answers are possible, output any of them.
Primer 1