All submissions for this problem are available.Chef is now a trained assassin, and his aim is to destroy and kill his enemy to avenge his father’s death. Being a trained assassin, Chef can easily enter into enemy’s territory. He uses this ability to enter the area where the army is residing into their tents. There are $N$ number of tents in this area having $ID$ $1,2,3..N$ . Some tents may be connected to each other via ropes. Chef wants to kill and injure as many warriors of army by burning the tents. If there are $c$ number of tents which are connected to each other via ropes, then Chef can light any one of these connected tents as warriors/soldiers of other $c-1$ tents will be alarmed by this activity. Suppose, Chef lights tent $X$ out of these $c$ tents, then all the warriors of the tent $X$ will get killed and the warriors which are in the rest of the connected tents i.e. $c-1$ tents will get injured. See sample explanation for more details. - Note If tent $1$ is connected to tent $2$, the tent $2$ is also connected to tent $1$. If tent $1$ is connected to tent $2$ and tent $2$ is connected to tent $3$, then tent $1$ is also connected with tent $3$. Now, Chef wants to kill maximum no. of soldiers of his enemie's army. Can you tell in advance how many soldiers will be killed and how many will get injured by this act of Chef? Also output the number (ID) of tents which will be lighten by Chef. If more than one connected tents can be lighten then Chef will choose to light the tent whose $ID$ will be minimum. ### Input: - First line contains a single integer 'T' the number of testcases. - First line of each test case will contain two space separated integers N and M, i.e. the total number of tents and total number of connections between the tents. - Second line of each test case will contain ‘N’ space separated integers denoting the number of soldiers in i’th tent 1<=i<=N. - Next ‘M’ lines contains two spaced separated ‘a’ and ‘b’ denoting Tent ‘a’ and Tent ‘b’ are connected to each other via rope. ### Output: - Two space separated integers denoting number of soldiers killed and number of soldiers injured respectively. - Next line contains the space separated ID of the lighten tents in increasing order of their ID’s. ### Constraints: - $1 \leq N \leq 10000$ - $1\leq M \leq 10000$ - $1\leq No. of soldiers in each tent \leq10000$ ### Sample Input 1 6 4 3 4 3 2 4 5 1 3 3 5 5 2 4 6 ### Sample Output: 9 12 2 6 ### Explaination Chef can choose 2nd and 6th tent.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.