Odd Opportunities

A secret worldwide organization operates in complete secrecy. Each member keeps contact with some of the other members, but not necessarily with all of them.

The newly elected head of the organization has a plan to make it even more secretive: some members will have to drop some of their contacts and stop communicating with them. What matters is only whether the number of contacts each member keeps ends up odd or even. Every member has been told whether the number of contacts they keep must be odd or must be even.

Your task is to decide whether the members can drop contacts so that every member's parity requirement is satisfied.

The input consists of several scenarios. Each scenario starts with a line containing two integers $V$ and $E$: $V$ is the number of members ($1 \le V \le 10000$) and $E$ is the number of contacts ($0 \le E \le V \cdot (V - 1) / 2$).

Each of the next $E$ lines contains two integers $v_1$ and $v_2$ ($1 \le v_1, v_2 \le V$, $v_1 \ne v_2$), meaning there is a contact between members $v_1$ and $v_2$. No pair of members appears more than once.

The next line contains exactly $V$ lowercase characters. The $i$-th character describes member $i$ and is either o (the number of contacts kept must be odd) or e (the number of contacts kept must be even).

The last scenario is followed by a line containing two zeros.

For each scenario, print possible if the members can drop contacts so that every member keeps a number of contacts of the required parity, and impossible otherwise. Print each answer on its own line.