---

Hello, Please anyone that know how to solve this problem help me. I really need the help. Thank you before hand.

Diplomatic Dinner You have been given a chance to apply for a job at your country's State Department. All you have to do in order to show you are qualified is arrange the seating of diplomats from other countries at a dinner party. You will be inviting 9 diplomats from several countries around the world. Each diplomat speaks from one to five languages. Diplomats not speaking a common language cannot talk to each other. Furthermore, some of the countries represented will not have diplomatic relations with other nations at the part, so these diplomats will not speak to each other either. Your task is to determine the seating arrangement at the dinner table for your leader and the 9 guests such that each person can speak to the person seated on each side. The round dinner table seats 10 people. The president of your own country will be seated at the first position at the table. The other positions will be numbered clockwise from 2 to 10. The person seated to the left of your president is in seat number 2 and the person seated to the right of your president is in seat number 10. Persons seated next to each other must speak a common language. A person may speak to the person on the left in one common language, and speak to the person on the right in another language. The governments of the guests seated next to each other must have formally recognized each other. Your government has diplomatic relations with the governments of all of his guests. The government of a guest may or may not have diplomatic relations with the governments of all the other guests. Two diplomats from the same country will have diplomatic relations with the same list of countries. A country will always have diplomatic relations with itself. Diplomats from the same country may or may not speak any languages in common. Input Input to the program will contain several data sets. Each data set will be a list of 10 people, one per line, ended by a blank line. The first line will represent your president, the other lines will represent the guest diplomats. Each line consists of a sequence of words, where words are separated by a single space. Each word is a sequence of capitals. The first word consists of 3 characters and represents the code for the guest's country. The second word contains 1 to 5 characters and represents the languages spoken by the guest. Each language a guest speaks is represented by a single letter. Finally, there is a list of up to 9 three-character words representing the codes of the countries of the other guests that this guest's government has diplomatic relations with. Output 10. More than one solution may exist, but you need find only one. If no solution is found, output the word IMPOSSIBLE. Print a blank line after each data set. Sample Input USA CHN GBR USR FRA FRG JPN ISR POR KOR TLC TQA DAO FHH NUW EF CHN GBR USR FRA FRG JPN ISR POR KOR CFE USA GBR FRA FRG ER USA CHN USR FRA FRG JPN ISR POR KOR RF USA GBR FRA FRG F USA CHN GBR USR FRG JPN ISR POR ERG USA CHN GBR USR FRA JPN ISR POR JHG USA GBR FRA FRG JPN ISR POR KOR HER USA GBR FRA FRG JPN KOR PGE USA GBR FRA FRG JPN KEC USA GBR USR JPN ISR ADBE TQA DAO FHH NUW FAB PSR FEQ QPA KCW EB TLC DAO PSR FEQ KCW B TLC TQA FHH FAB PSR FEQ QPA KCW B TLC DAO PSR KCW DBE TLCFAB PSR FEQ QPA KCW D TLC DAO PSR FEQ QPA AC TLC TQA DAO FHH FAB QPA CB TLC TQA DAO FAB QPA D TLC DAO FAB PSR FEQ KCW AE TLC TQA DAO FHH QPA Sample Output 1 F USA E 2 E CHN E 3 E GBR E 4 E KOR E 5 E ISR H 6 H JPN G 7 G POR E 8 E FRG R 9 R USR F 10 F FRA F IMPOSSIBLE ************************* Notes *************************** If you're thinking this problem calls for generating permutations, you're right. Here's some sample code that forms permutations. Of course, there's lots of code on the Internet for doing this sort of thing: void usePermutation() { // do something with the permutation here } int[] indexes; int level; int numJobs = void visit(int k) { int i; level++; indexes[k] = level; if (level == numJobs) usePermutation(); else { for ( i = 0; i < numJobs; i++ ) { if (indexes[i] == 0) visit(i); } } level--; indexes[k] = 0; } Calling code: level = -1; int INDEX_SIZE = 9; indexes = new int[INDEX_SIZE]; for(int j=0; j < INDEX_SIZE; j++) indexes[j] = 0; visit(0);