The Dining Diplomats Diplomats from several countries are together for a summit. The banquet on the last day of the summit is to be served at a big round table. The organisers need to _nalise a seating arrangement for the diplomats. Some pairs of diplomats are known to be friendly to each other, and some other pairs are known to be foes of each other. Some diplomats are indi_erent to all the other diplomats. The organisers would like to design a seating chart so that no two foes are seated next to each other, unless at least one of them is also seated next to a friend, and the other is seated next to a friend or an indi_erent diplomat. Write a C++ program that given the facts about friends, foes and indi_erent diplomats, generates a seating arrangement, if any, that satis_es the above condition. If no such seating arrangement exists, theprogram should output a suitable message. Input The input will have several lines of input. Each line may have two names and one integer (1 for friend, and 0 for foe), or just one name for diplomats that are indi_erent to all the others. The string of characters containing the name may contain non-letters; they should not be included in the name. Some of the letters in the name may be in upper case. These, except the _rst letter, should be converted to lower case. Names and numbers may be separated by one or more blank spaces (' '), and/or tab characters ('nt'). On each line, there may be one or more blank spaces (' '), and/or tab characters ('nt') before the end of line character ('nn'). For example, consider the following input: Jo4e Ma,ry 1 ElizaBet5h June 1 Joe John 0 Joe, JuNe 0 John JUne 1 Margaret The above input indicates that there are 6 diplomats attending the summit: Joe, Mary, Elizabeth, June, John, and Margaret. The friend pairs are Joe and Mary, Elizabeth and June and John and June. The foe pairs are Joe and John, and Joe and June. Margaret is indi_erent to all the others. You may assume that only those diplomats whose names are included in the input _le will be at the summit. If a pair of diplomats, say A and B, appear in the input, but do not appear as either a pair of friends, or a pair of foes, you may assume that they are indi_erent to each other. You may assume that the input _le is not contradictory, i.e., if two diplomats are listed as friends, then they will not be listed as foes, nor will either of them be listed as being indi_erent. Similarly, if two diplomats are listed as foes, they will not be listed as friends, nor will either of them be listed as being indi_erent. If diplomat A is listed as a friend (respectively, foe) of diplomat B, then this implies that B is a friend (respectively, foe) of A. Output Your program should _rst output the names of all the diplomats at the summit in alphabetical order. Then, your program should output a possible seating arrangement, if one exists. If no seating arrangement is possible, then your program should print a suitable message. For the above input, your program could output: Diplomats: Elizabeth, Joe, John, June, Margaret, Mary. Seating Arrangement: Joe, Mary, Elizabeth, June, John, Margaret. Note that, since the banquet is at a round table, Margaret is seated next to Joe. Note that for a given input, there may be several possible seating arrangements. For example, for the above input, another possible seating arrangement is: Joe, John, June, Mary, Elizabeth, Margaret In this case the two foes Joe and John are seated next to each other, but John has a friend in June also seated next to him, and Joe has Margaret, an indi_erent diplomat, seated next to him. If multiple seating arrangements exist, your program can output any one of these possible seating arrangements.