29942번 - Lining up Children 스페셜 저지다국어

After a field trip, the teacher needs to line up all children in order to count them and verify that none are missing. Anyone who has ever had to deal with children knows how difficult this can be. A child absolutely must stand next to each of their friends, otherwise a riot will soon occur.

Find one possible way to order the children such that all children are satisfied.

The first line of input contains two space-separated integers $N$ and $M$---the number of children and the number of pairs who are friends ($1 \le N \le 10^5$, $1 \le M \le 3 \cdot 10^5$).

The next line contains $N$ space-separated strings---the names of the children. Names are at most 10 symbols long and consist of only uppercase and lowercase Latin letters and dashes. It is guaranteed that each child has a name different from the rest.

Then follow $M$ lines, each containing two space-separated names, denoting a pair of friends.

The first line of output should contain SAAB if a solution is possible, or EI SAA, if it is not. If a solution is possible, output on the second line the list of names in an order that would satisfy all children.