See Aufgabe1.
A solution to the 1st problem of the 38th Bundeswettbewerb Informatik (German Olympiad in Informatics)