Problem H: Treasure

It is rumored that many centuries ago, pirates had hidden priceless treasure on a remote island. You are in charge of an expedition to recover the treasure. You land on the island and find a big mountain, inside which a big network of caves has been built. There are narrow passages connecting some of the caves to each other. You find that in every cave either a big X or + sign is drawn. On searching further, you find an old manuscript giving a complete map of the caves and the passages connecting them. At the bottom is a note which says that the treasure is buried below the ground in some of the caves. The note also says that the marks X and + are clues to find the caves below which the treasure is hidden. It says that a cave C is marked X if there are an odd number of neighboring caves containing the treasure else it is marked +. A neighboring cave of C is one to which there is a direct passage from C without going through any other cave. The note also says that the construction of the caves and passages is such that this information is sufficient to uniquely identify the caves below which the treasure is hidden. You have to write a program to find out these caves from the given information.

Input

The input will consist of several test cases. The first line of each test case will specify $n$, the number of caves, assumed to be numbered from 0 to $n$-1. If $n$ is 0, it indicates end of input. The value of $n$ will be at most 100. The next line will give $m$, the total number of passages. The next $m$ lines will contain two integers each, specifying the two caves connected by each passage. The next $n$ lines will give the marking on each cave, one per line, from cave number 0 to $n$-1. The mark is given as a single character either 'X' or '+'.

Output

For every test case, the output should be the numbers (one per line, in increasing order) of the caves below which the treasure is hidden. Output lines for each case should be followed (immediately, without any blank lines) by the output lines for the next test case.

Sample Input

2
1
0 1
X
+
4
4
0 1
1 2
1 3
2 3
+
+
+
X
0

Sample Output

1
0
2