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:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS 
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. 