The Trading Topology
All submissions for this problem are available.
Sheldon is designing a game like AOE(Age Of Empires). In that game a player will make his empire consisting of many cities and towns. The empire is such , though each city is not directly connected to all other cities, but there exist transportation routes such that from one city materials and goods can be send to any other city. After the players make their empires they may declare war on others empires. Now during war time there is excessive need of resources and transportation is heavily used. If the empire is designed in such a way, that destroying any city breaks the empire into many parts with no possible transportation between those parts.Then opponent can take advantage of that and destroy those particular cities first(by aerial attack).
Such cities are called 'Critical Cities'.
Leonard becomes very interested in that game. And discusses what could be the possible strategies for designing an empire. Leonard makes possible empire design showing how cities are connected and Sheldon points out 'Critical cities' in Leonard's empire. Now Sheldon is bored of it , and he needs a program which can find out critical cities given the input as the design of empire. Your task is to help Sheldon.
First line contains the number of test cases 'T'.
For each test case first line contains two integer 'N'(number of cities) and 'K'(number of transportation roads) subsequent 'K' lines contains two integers 'U' and 'V', showing that there is a bidirectional transportation road between 'U' and 'V'. 'U' and 'V' are 1 based indices of cities.
'T' lines for each test case.
Each line contains
Number of critical cities followed by the indices of crtitical cities in ascending order.
1 <= T <= 100
1 <= N <= 1000
1 <= K <= (N * (N - 1)) / 2
1 <= U, V <= N
U != V
Input: 2 5 4 5 1 5 2 5 3 5 4 6 5 2 1 2 3 5 4 5 6 5 2 Output: 1 5 2 2 5
|Time Limit:||0.106383 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.5, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.