We will use the trie data structure to solve the task. Explanation of trie can be found on many places, we recommend Codeforces, Wikipedia, Topcoder.

In short, a trie is a tree with an empty string in the root, and letters in other vertices. When we build a trie using some set of strings, by concatenating all letters on some path from the root to some other vertex, we can get all strings from the set and their prefixes.

Trie for the first example is:

We build the trie using all of Nina's and Emilija's words. We color the vertices that are ends of Nina's words blue, and vertices that are ends of Emilija's words red. (It is possible that a vertex is both blue and red.) The game starts in the root, and a move is just traversing some downward edge of the current vertex. Nina is on the move on even levels, and Emilija on odd levels.

Nina can make a move if there exists some blue vertex in that child's subtree, and the same thing holds for Emilija and red vertices.

The winner can be determined by simple dynamic programming. We can calculate this from the bottom to the top. The player that is on the move wins if she can move to a vertex in which she also wins, otherwise the other player wins. The answer is the winner in the root.