50118. Connect Integers

I'm a slow walker, but I never walk backwards.

Task Description

We have many positive integers, and we want to find the maximum length of the connected integer sequence. Two integers are connected if the LSD (Least Significant Digit) of the previous number is as same as the MSB (Most Significant Digit) of the current number.

For example, if we have three integers “1234”, “432”, and “12” as a sequence.

samplesample

The maximum length of the connected integer sequence is 7, which is the sum of the length of “1234” and “432”. Note that "432" is NOT connected to "12" since 2 from "432" is not the same as the 1 from "12". Also note that the maximum length sequence could be anywhere within the sequence of numbers, not necessarily from the beginning.

Input Format

The input has one line of positive integers. There is a least one number in the input and you must process all of them until EOF.

Output Format

The output is the maximum length of connected integer sequence.

Subtask

  • 10 points: There is only one integer in the input.
  • 10 points: No integers are connected.
  • 80 points: No restriction on the positive integers.

Sample Input 1

123

Sample Output 1

3

Sample Input 2

19 84 654 2145012300 1

Sample Output 2

10

Sample Input 3

1 12 234 5 6789 9101112

Sample Output 3

11

Hint

You can get the most significant digit and the number of digits of a number by repeatedly dividing it by 10, until it is less than 10. For example if the number is 362, then you get 36, then you get 3, which is less than 10. You get to this by 2 steps, so the number of digits is 3.

Discussion