2721. Javanese Cryptoanalysis

单点时限: 5.0 sec

内存限制: 256 MB

Javanese is the language of the people in the Central and Eastern parts of the island of Java, Indonesia.

In 1926, a standard orthography using the English Alphabet was created for the Javanese language. This writing system uses all letters from A to Z. The five letters A, E, I, O, and U are vowels, while all other letters are consonants. In Javanese words vowels and consonants always alternate. This property is quite useful when deciphering encrypted Javanese texts.

A text $s$ consists of words, each word contains only capital letters. Let’s call text $s$ legitimate if in each word of $s$ vowels and consonants alternate (no two vowels and no two consonants are located next to each other).

A simple substitution cipher is applied to a text $s$. That is, a bijection $f : A \rightarrow A$ is chosen, where $A$ is the set of capital letters. The encoded text $t$ is obtained from $s$ by substituting each letter $c$ with $f(c)$.

You’re given the encoded text $t$. Find any legitimate text $s$ that can be encoded as $t$, or detect that there is no such legitimate $s$.

输入格式

The input file contains the encoded text $t$, a list of words separated by spaces and/or line breaks. Each word consists only of capital letters (A to Z).

The input file contains no more than $100~000$ characters.

输出格式

If the text $t$ cannot be an encoded legitimate text, output only one word impossible.

Otherwise, output any legitimate text $s$ that can be encoded into $t$. Separate words of $s$ with spaces and/or line breaks. All letters in $s$ should be capital.

样例

Input
NEERC
Output
impossible
Input
O RISK LIP FOCUS LUCKY
Output
A CODE FOR VALID FILES

7 人解决,11 人已尝试。

148 份提交通过,共有 168 份提交。

5.9 EMB 奖励。

创建: 11 年,12 月前.

修改: 2 年,10 月前.

最后提交: 8 月,2 周前.

来源: NEERC 2008

题目标签