Lining up Children

Interview

Time limit1sMemory limit1024 MB

Summary

Given friend pairs among N children, find a line order where every friend pair stands next to each other, or report that no such order exists.

Level: Medium4 of 10
Topics: Graph, Union-find, Implementation
Solved: No attempts yet

Problem

After a field trip, a teacher has to line up all the children to count them and check that none are missing. Anyone who has dealt with children knows how hard this is. Every child must stand next to each of their friends, or a riot will soon break out.

Find one order of the children that satisfies all of them.

Input

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

The next line contains $N$ space-separated names of the children. Each name is at most 10 characters long and uses only uppercase and lowercase Latin letters and dashes. All names are different.

The following $M$ lines each contain two space-separated names, which form a pair of friends.

Output

If a solution exists, print SAAB on the first line and the names in a valid order on the second line. If no solution exists, print EI SAA.

Examples2

Example 1

Input

5 3
Bob Carol Eve Dave Alice
Alice Carol
Alice Bob
Dave Eve

Expected output

SAAB
Bob Alice Carol Eve Dave

Example 2

Input

3 3
Regina Gretchen Karen
Regina Gretchen
Gretchen Karen
Regina Karen

Expected output

EI SAA