홀짝 연락망 정리

전 세계에 걸쳐 완전히 비밀리에 활동하는 한 조직이 있다. 각 구성원은 다른 구성원들 중 일부와 연락을 주고받지만, 반드시 모두와 연락하는 것은 아니다.

새로 선출된 조직의 수장은 조직을 더욱 은밀하게 만들 계획을 세웠다. 일부 구성원은 자신의 연락 중 일부를 끊고 더 이상 그 상대와 연락하지 않아야 한다. 중요한 것은 각 구성원이 유지하는 연락의 수가 홀수인지 짝수인지 여부뿐이다. 모든 구성원은 자신이 유지해야 하는 연락의 수가 홀수여야 하는지 짝수여야 하는지를 지시받았다.

각 구성원이 연락을 끊어서 모든 구성원의 홀짝 조건을 만족시킬 수 있는지 판정하는 것이 당신의 과제이다.

입력은 여러 개의 시나리오로 이루어진다. 각 시나리오는 두 정수 $V$와 $E$가 주어지는 줄로 시작한다. $V$는 구성원의 수이고 ($1 \le V \le 10000$), $E$는 연락의 총 개수이다 ($0 \le E \le V \cdot (V - 1) / 2$).

이어지는 $E$개의 줄에는 각각 두 정수 $v_1$과 $v_2$가 주어진다 ($1 \le v_1, v_2 \le V$, $v_1 \ne v_2$). 이는 구성원 $v_1$과 $v_2$ 사이에 연락이 있음을 뜻한다. 같은 쌍은 두 번 이상 나타나지 않는다.

그다음 줄에는 정확히 $V$개의 소문자가 주어진다. $i$번째 문자는 구성원 $i$에 대응하며, o(유지하는 연락의 수가 홀수여야 함) 또는 e(유지하는 연락의 수가 짝수여야 함) 중 하나이다.

마지막 시나리오 다음에는 두 개의 0이 적힌 줄이 주어진다.

각 시나리오마다, 모든 구성원이 요구된 홀짝 조건에 맞는 수의 연락을 유지하도록 연락을 끊을 수 있으면 possible을, 그렇지 않으면 impossible을 각각 한 줄에 출력한다.