Chef and Digit Jumps

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Chef loves games! But he likes to invent his own. Now he plays game "Digit Jump". Chef has sequence of digits S_{1}, S_{2},..., S_{N},. He is staying in the first digit (S_{1}) and want to reach the last digit (S_{N}) in the minimal number of jumps.
While staying in some digit x with index i (digit S_{i}) Chef can jump into digits with indices i  1 (S_{i1}) and i + 1 (S_{i+1}) but he can't jump out from sequence. Or he can jump into any digit with the same value x.
Help Chef to find the minimal number of jumps he need to reach digit S_{N} from digit S_{1}.
Input
Input contains a single line consist of string S of length N the sequence of digits.
Output
In a single line print single integer  the minimal number of jumps he needs.
Constraints
 1 ≤ N ≤ 10^5
 Each symbol of S is a digit from 0 to 9.
Example
Input: 01234567890 Output: 1 Input: 012134444444443 Output: 4
Explanation
In the first case Chef can directly jump from the first digit (it is 0) to the last (as it is also 0).
In the second case Chef should jump in such sequence (the number of digits from 1: 124515).
Author:  berezin 
Tester:  shiplu 
Editorial  http://discuss.codechef.com/problems/DIGJUMP 
Tags  berezin bfs dijkstra easy june14 
Date Added:  12032014 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.4, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 
When i submit my code
can any one one give me more
The 2nd example's
@coolworks The numbers given
Dear All, i tried many times
can anyone provide some
Now it sickening me ... plz
Hi Can anybody help me out in
I am getting NZEC error on