Medium Beginners Problems > Ad-hoc

Rahim and Karim are good friends. One day Karim gives Rahim a challenge of coins. Karim gives Rahim N coins but there was no integer number written on each coin’s body (So Rahim can’t understand each coin's value). Then Karim gives Rahim Q queries, from these query Rahim has to determine the coin's value and has to rearrange the coins serially in increasing order on the table. If it is impossible to rearrange the coins say “Impossible”. But Rahim is confused of queries so he needs your help. Write a program that helps Rahim. ***Constraints : 2<=N<=26 , 2<=Q<=35*** Input Specification: -------------------- You will be given an integer **T** denoting the number of test cases, then **T** lines followes: In each test case there will be two numbers **N** and **Q**, denoting number of queries. Then there will **Q** lines, in each line there will be a String. For example : **“A>B”** here **A** means a coin , **B** means another coin. **A>B** means **A** is greater than **B** in value. Output Specification: --------------------- For each test case print the rearrangements of coins in increasing order. If it is impossible to rearrange the coins, print **“Impossible”** without quotes. See the simple input/output for better understanding. Sample Input : ------- 2 3 3 A>B C<B A>C 3 3 A<C B<A B>C Sample Output: ------- CBA Impossible **EXPLANATION :** In first test case, Since A>B , B>C , A>C So answer is CBA, means C is the smallest value coin, then B is greater than C but smaller than A, then A is the greatest coin than C and B. C is smallest , B is little bit greater, A is the greatest coin in value. In the second test case, it is impossible because we cannot create an increasing sequence.

Abdullah Mohammad Daihan