Training Site
Sideways banner

Lost Shoes

Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 126 megabytes
Time limit: 1.0 seconds

The principal of the school insists kids take their shoes off outside the classroom. On any one day there are varying numbers of pairs of shoes and sometimes a kid has temporarily lost one (children will be children!). And of course they are all over the place outside the room, not in nice neat pairs.
The possible shoe colours are Green, Black, Red, Blue, Brown, and Mustard. Please help the principal by finding out which shoes don’t have a full pair.

Input Format

To simplify matters the assistant mentally thinks G for Green, B for Black, R for Red, Bl for Blue, Br for Brown, and M for Mustard. The input will be a string of those letters, representing the shoes that the assistant has found.

Output Format

For each shoe that doesn't have a full pair, output a new line containing a sentence in the following format:

A <<Colour>> shoe has no partner.
For example, if there is Blue shoe that is missing a partner, output
A Blue shoe has no partner.

If there are multiple colours that don't have full pairs, output them in the order of their colours. Green shoes should be first in the output, followed by Black, Red, Blue, Brown and finally Mustard. If no colour is missing shoes, output the following instead:
All paired up!


It is guaranteed that there will be at least 1 and no more than 50 shoes in the input.


  • Subtask 1 (+31%): The input contains only Green shoes.
  • Subtask 2 (+33%): The input contains only Green, Black, Red, and Mustard shoes.
  • Subtask 3 (+36%): No further constraints apply.
  • Sample Input 1


    Sample Output 1

    A Green shoe has no partner.
  • Sample Input 2


    Sample Output 2

    A Black shoe has no partner.
    A Red shoe has no partner.
    A Blue shoe has no partner.
    A Mustard shoe has no partner.
  • Sample Input 3


    Sample Output 3

    All paired up!