Pintura Rubro-Negra

O Flamengo está organizando um mosaico gigante no Maracanã em homenagem à vitória do seu tetracampeonato da Libertadores. Cada um dos N setores pode ser pintado nas cores tradicionais do Mengão.

Os setores são conectados por $M$ passagens. Por regra de organização, setores conectados diretamente devem ter cores diferentes.

Para garantir que essa regra possa ser seguida, o conjunto de setores e passagens deve formar um grafo bipartido, ou seja, não pode existir nenhum ciclo de comprimento ímpar. Caso contrário, seria impossível colorir todos os setores mantendo a alternância de cores.

A pintura começa em um setor inicial $S$, que recebe uma cor inicial $(PRETA$ ou $VERMELHA)$.
A partir disso, a pintura se propaga:

• Cada setor pintado força todos os seus vizinhos a receberem a cor oposta.
  
• Esse processo continua até todas as áreas alcançáveis estarem definidas.

Dado um setor $T$, determine qual cor ele terá ao final.

Entrada

• A primeir linha contém dois inteiros $N$ e $M$ ($1 \le N \le 10^5$, $1 \le M \le 2 \times 10^5$), representando o número de setores e o número de passagens entre eles.
• As próximas $M$ linhas contêm dois inteiros $u$ e $v$ ($1 \le u, v \le N$), indicando que existe uma passagem entre os setores $u$ e $v$.
• A próxima linha contém um inteiro $S$ ($1 \le S \le N$) que representa o setor inicial do mosaico, uma string $C$ que representa a cor $(PRETA$ ou $VERMELHA)$ e um setor $T$ ($1 \le T \le N$), que reprenta o setor que queremos descobrir a cor.

Saída

• Imprima uma única linha contendo a cor do setor $T$ ao final da pintura.

Exemplo 1

Entrada

9 8
1 2
2 3
2 4
4 6
2 5
5 7
3 8
3 9
2 PRETA 6

Saída

PRETA