Chef loves games! But he likes to invent his own. Now he plays game "Digit Jump". Chef has a sequence of digits $S_{1}, S_{2}, \ldots , S_{N}$. He is staying in the first digit $S_{1}$ and wants to reach the last digit $S_{N}$ in the minimal number of jumps. 
While staying in some index $i$ Chef can jump into $i - 1$ and $i + 1$, but he can't jump out from sequence. Or he can jump into any digit with the same value $S_i$. 
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\leq N \leq 10^5$
- Each symbol of $S$ is a digit from $0$ to $9$. 

-----Example Input 1-----
01234567890

-----Example Output 1-----
1

-----Example Input 2-----
012134444444443

-----Example Output 2-----
4

-----Explanation-----
Test Case 1: Chef can directly jump from the first digit (it is $0$) to the last (as it is also $0$).
Test Case 2: Chef should follow the following path: $1 - 2 - 4 - 5 - 15$.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: String algorithms

Graph algorithms

Data structures

Graph traversal


Solutions:
import heapq

def digitJump(text):
	L = len(text)
	if L == 1 or L == 2:
		return L - 1
	numPos = [[] for i in range(10)]
	minJump = [2000000 for _ in range(L)]
	minJump[L - 1] = 0
	maxJumpForNum = [2000000 for _ in range(10)]
	for i in range(L):
		numPos[int(text[i])].append(i)
	h = []
	heapq.heappush(h, (0, int(text[L - 1]), L - 1))
	while len(h) > 0:
		(minJ, num, idx) = heapq.heappop(h)
		setJump = minJ + 1
		if maxJumpForNum[num] > setJump:
			maxJumpForNum[num] = setJump
			for i in numPos[num]:
				if i == idx:
					continue
				if minJump[i] > setJump:
					minJump[i] = setJump
					heapq.heappush(h, (setJump, num, i))
		if idx > 0:
			if minJump[idx - 1] > setJump:
				minJump[idx - 1] = setJump
				heapq.heappush(h, (setJump, int(text[idx - 1]), idx - 1))
		if idx < L - 2:
			if minJump[idx + 1] > setJump:
				minJump[idx + 1] = setJump
				heapq.heappush(h, (setJump, int(text[idx + 1]), idx + 1))
	return minJump[0]

def __starting_point():
	text = input().strip()
	print(digitJump(text))
__starting_point()


from collections import deque, defaultdict
s = input().strip()
length = len(s)
adj = defaultdict(list)
distance = [0] * length
visited = [0] * length
for index in range(length):
	char = s[index]
	adj[char].append(index)
queue = [0]
visited[0] = 1
while len(queue) != 0:
	front = queue.pop(0)
	if front == length - 1:
		break
	for j in range(len(adj[s[front]])):
		next_index = adj[s[front]][j]
		if visited[next_index] == 0:
			visited[next_index] = 1
			queue.append(next_index)
			distance[next_index] = distance[front] + 1
	adj[s[front]].clear()
	if front - 1 >= 0 and front - 1 < length:
		if visited[front - 1] == 0:
			visited[front - 1] = 1
			queue.append(front - 1)
			distance[front - 1] = distance[front] + 1
	if front + 1 >= 0 and front + 1 < length:
		if visited[front + 1] == 0:
			visited[front + 1] = 1
			queue.append(front + 1)
			distance[front + 1] = distance[front] + 1
print(distance[length - 1])


from queue import Queue
s = input().strip()
t = [[] for i in range(10)]
for a in range(len(s)):
	b = int(s[a])
	t[b].append(a)
digits = [-1] * len(s)
digits[0] = 0
q = Queue()
q.put(0)
while not q.empty():
	if digits[len(s) - 1] != -1:
		break
	h = q.get(0)
	value = int(s[h])
	for c in t[value]:
		if digits[c] == -1:
			digits[c] = digits[h] + 1
			q.put(c)
	t[value] = []
	if h + 1 < len(s) and digits[h + 1] == -1:
		digits[h + 1] = digits[h] + 1
		q.put(h + 1)
	if h - 1 > 0 and digits[h - 1] == -1:
		digits[h - 1] = digits[h] + 1
		q.put(h - 1)
print(digits[len(s) - 1])


s = input().strip()
ans = -1
L = []
for i in range(10):
	h = []
	L.append(h)
for i in range(0, len(s)):
	L[int(s[i])].append(i)
pos = [0] * 10
visited = [False] * len(s)
queue = [(0, 0)]
visited[0] = True
while queue:
	k = queue.pop(0)
	k1 = k[0]
	k2 = k[1]
	if k1 == len(s) - 1:
		ans = k2
		break
	if k1 - 1 >= 0:
		if visited[k1 - 1] == False:
			queue.append((k1 - 1, k2 + 1))
			visited[k1 - 1] = True
	if k1 + 1 <= len(s) - 1:
		if visited[k1 + 1] == False:
			queue.append((k1 + 1, k2 + 1))
			visited[k1 + 1] = True
	if pos[int(s[k1])] == 0:
		pos[int(s[k1])] = 1
		for i in L[int(s[k1])]:
			if visited[i] == False:
				queue.append((i, k2 + 1))
				visited[i] = True
print(ans)


from collections import *
mtrx = [int(x) for x in list(input().strip())]
length = len(mtrx)
numbros = [[] for i in range(10)]
for i in range(length):
	numbros[mtrx[i]].append(i)
distance = [-1] * length

def bfs(x):
	distance[x] = 0
	q = deque()
	q.append(x)
	while len(q) > 0:
		x = q.popleft()
		if x == length - 1:
			break
		if x - 1 >= 0 and distance[x - 1] == -1:
			q.append(x - 1)
			distance[x - 1] = distance[x] + 1
		if x + 1 <= length - 1 and distance[x + 1] == -1:
			q.append(x + 1)
			distance[x + 1] = distance[x] + 1
		for bro in numbros[mtrx[x]]:
			if distance[bro] == -1:
				distance[bro] = distance[x] + 1
				q.append(bro)
		numbros[mtrx[x]] = []
	return distance
print(bfs(0)[length - 1])


from collections import defaultdict
a = input().strip()
n = len(a)
g = defaultdict(list)
for i in range(n):
	g[a[i]].append(i)
vis = {}
vis[0] = 0
q = [0]
while len(q) != 0:
	tmp = q.pop(0)
	if tmp == n - 1:
		break
	val = a[tmp]
	s = len(g[val])
	for i in range(s):
		if g[val][i] not in vis:
			vis[g[val][i]] = vis[tmp] + 1
			q.append(g[val][i])
	g[val] = []
	if tmp + 1 <= n - 1 and tmp + 1 not in vis:
		q.append(tmp + 1)
		vis[tmp + 1] = vis[tmp] + 1
	if tmp - 1 >= 0 and tmp - 1 not in vis:
		q.append(tmp - 1)
		vis[tmp - 1] = vis[tmp] + 1
print(vis[n - 1])


s = input().strip()
n = len(s)
indices = []
for i in range(10):
	indices.append([])
for i in range(n):
	indices[int(s[i])].append(i)
q = []
dist = [-1 for i in range(n)]
q.append(0)
dist[0] = 0
while len(q) > 0:
	u = q.pop(0)
	if u - 1 >= 0 and dist[u - 1] == -1:
		dist[u - 1] = 1 + dist[u]
		q.append(u - 1)
	if u + 1 < n and dist[u + 1] == -1:
		dist[u + 1] = 1 + dist[u]
		q.append(u + 1)
	for v in indices[int(s[u])]:
		if dist[v] == -1:
			dist[v] = 1 + dist[u]
			q.append(v)
	indices[int(s[u])] = []
print(dist[n - 1])


from collections import defaultdict
from collections import deque
s = input().strip()
n = len(s)
dist = [0] * n
visited = [False] * n
d = defaultdict(list)
for i in range(n):
	d[s[i]].append(i)
visited[0] = True
stk = deque()
stk.append(0)
while stk:
	node = stk.popleft()
	if node == n - 1:
		break
	for i in d[s[node]]:
		if not visited[i] and i != node:
			dist[i] = dist[node] + 1
			visited[i] = True
			stk.append(i)
	d[s[node]] = []
	if node > 0 and (not visited[node - 1]):
		stk.append(node - 1)
		visited[node - 1] = True
		dist[node - 1] = dist[node] + 1
	if node < n - 1 and (not visited[node + 1]):
		stk.append(node + 1)
		visited[node + 1] = True
		dist[node + 1] = dist[node] + 1
print(dist[-1])


N = input().strip()
ij = [-1] * len(N)
vj = [True] * 10
ij[0] = 0
i = 0
q = -1
pos = [0]
while i < len(N):
	if vj[int(N[pos[i]])]:
		for j in range(len(N)):
			if N[j] == N[pos[i]] and ij[j] == -1:
				ij[j] = ij[pos[i]] + 1
				pos.append(j)
				if j == len(N) - 1:
					q = len(N)
	vj[int(N[pos[i]])] = False
	if pos[i] - 1 >= 0 and ij[pos[i] - 1] == -1:
		ij[pos[i] - 1] = ij[pos[i]] + 1
		pos.append(pos[i] - 1)
	if pos[i] + 1 <= len(N) - 1 and ij[pos[i] + 1] == -1:
		ij[pos[i] + 1] = ij[pos[i]] + 1
		pos.append(pos[i] + 1)
	i += 1
	if q == len(N):
		i = q
print(ij[-1])


import queue
s = [int(x) for x in input().strip()]
N = len(s)
(dist, a) = ([-1 for _ in range(N)], [[] for _ in range(10)])
for i in range(N):
	a[s[i]].append(i)
seen = queue.Queue()
seen.put(0)
dist[0] = 0
while seen.qsize() > 0:
	idx = seen.get()
	if idx > 0 and dist[idx - 1] == -1:
		dist[idx - 1] = dist[idx] + 1
		seen.put(idx - 1)
	if idx < len(s) - 1 and dist[idx + 1] == -1:
		dist[idx + 1] = dist[idx] + 1
		seen.put(idx + 1)
	for v in a[s[idx]]:
		if dist[v] == -1:
			dist[v] = dist[idx] + 1
			seen.put(v)
	a[s[idx]].clear()
print(dist[-1])


__author__ = 'Ronald Kaiser'
__email__ = 'raios dot catodicos at gmail dot com'
S = list(map(int, input().strip()))
a = [[] for _ in range(10)]
[a[v].append(i) for (i, v) in enumerate(S)]
d = [False] * 10
ml = [(False, -1)] * len(S)
ml[0] = (True, 0)
q = [0]
while q:
	cur = q.pop(0)
	if cur == len(S) - 1:
		print(ml[cur][1])
		break
	for adj in [cur - 1, cur + 1]:
		if not 0 <= adj < len(S) or ml[adj][0]:
			continue
		ml[adj] = (True, ml[cur][1] + 1)
		q.append(adj)
	if d[S[cur]]:
		continue
	d[S[cur]] = True
	for p in a[S[cur]]:
		if ml[p][0]:
			continue
		ml[p] = (True, ml[cur][1] + 1)
		q.append(p)


import queue

def chef_digit_jump(digits):
	Q = queue.Queue()
	Q.put(0)
	dist = [-1 for i in range(len(digits))]
	dist[0] = 0
	position = [[] for i in range(10)]
	n = len(digits)
	for i in range(n):
		position[ord(digits[i]) - 48].append(i)
	while Q.qsize() > 0:
		u = Q.get()
		if u - 1 >= 0 and dist[u - 1] == -1:
			dist[u - 1] = dist[u] + 1
			Q.put(u - 1)
		if u + 1 < n and dist[u + 1] == -1:
			dist[u + 1] = dist[u] + 1
			Q.put(u + 1)
		for j in position[ord(digits[u]) - 48]:
			if digits[u] == digits[j] and dist[j] == -1:
				Q.put(j)
				dist[j] = dist[u] + 1
		position[ord(digits[u]) - 48].clear()
	return dist[n - 1]
a = input().strip()
print(chef_digit_jump(a))


from queue import Queue
s = input().strip()
neighbours = [[] for i in range(10)]
for i in range(len(s)):
	temp = int(s[i])
	neighbours[temp].append(i)
digits = [-1] * len(s)
digits[0] = 0
q = Queue()
q.put(0)
while not q.empty():
	if digits[len(s) - 1] != -1:
		break
	currentNode = q.get(0)
	value = int(s[currentNode])
	for i in neighbours[value]:
		if digits[i] == -1:
			digits[i] = digits[currentNode] + 1
			q.put(i)
	neighbours[value] = []
	if currentNode + 1 < len(s) and digits[currentNode + 1] == -1:
		digits[currentNode + 1] = digits[currentNode] + 1
		q.put(currentNode + 1)
	if currentNode - 1 > 0 and digits[currentNode - 1] == -1:
		digits[currentNode - 1] = digits[currentNode] + 1
		q.put(currentNode - 1)
print(digits[len(s) - 1])


import copy
import sys
from collections import defaultdict, Counter

def input():
	return sys.stdin.readline()

def mapi():
	return map(int, input().split())

def maps():
	return map(str, input().split())

def print(arg, *argv, end=None):
	sys.stdout.write(str(arg))
	for i in argv:
		sys.stdout.write(' ' + str(i))
	sys.stdout.write(end) if end else sys.stdout.write('\n')

def solve():
	t = 1
	while t:
		t -= 1
		a = input().strip()
		n = len(a)
		g = defaultdict(list)
		for i in range(n):
			g[a[i]].append(i)
		vis = {}
		vis[0] = 0
		q = [0]
		while len(q) != 0:
			tmp = q.pop(0)
			if tmp == n - 1:
				break
			val = a[tmp]
			x = len(g[val])
			for i in range(x):
				if g[val][i] not in vis:
					q.append(g[val][i])
					vis[g[val][i]] = vis[tmp] + 1
			g[val] = []
			if tmp + 1 <= n - 1 and tmp + 1 not in vis:
				q.append(tmp + 1)
				vis[tmp + 1] = vis[tmp] + 1
			if tmp - 1 >= 0 and tmp - 1 not in vis:
				q.append(tmp - 1)
				vis[tmp - 1] = vis[tmp] + 1
		print(vis[n - 1])

def __starting_point():
	solve()
__starting_point()


from collections import defaultdict
from collections import deque
g = defaultdict(lambda : [])
s = input().strip()
ls = len(s)
vis = [False for i in range(ls)]
dis = [0 for i in range(ls)]
for i in range(1, ls):
	g[s[i]].append(i)
que = deque()
que.append(0)
vis[0] = True
while que:
	indx = que.popleft()
	if indx == ls - 1:
		break
	temp = s[indx]
	for i in g[temp]:
		if not vis[i]:
			vis[i] = True
			que.append(i)
			dis[i] = dis[indx] + 1
	g[temp].clear()
	if indx - 1 >= 0 and (not vis[indx - 1]):
		vis[indx - 1] = True
		que.append(indx - 1)
		dis[indx - 1] = dis[indx] + 1
	if indx + 1 < ls and (not vis[indx + 1]):
		vis[indx + 1] = True
		que.append(indx + 1)
		dis[indx + 1] = dis[indx] + 1
print(dis[-1])


from queue import Queue
S = list(map(int, input().strip()))
N = len(S)
graph = {}
for i in range(N):
	graph[S[i]] = []
if N > 1:
	for i in range(N):
		graph[S[i]].append(i)
	visited = [0] * N
	distance = [0] * N
	Q = Queue()
	Q.put(0)
	while not Q.empty():
		t = Q.get()
		for i in graph[S[t]]:
			if visited[i] == 0 and i != t:
				Q.put(i)
				visited[i] = 1
				distance[i] = distance[t] + 1
		graph[S[t]] = []
		if t > 0:
			if visited[t - 1] == 0:
				Q.put(t - 1)
				visited[t - 1] = 1
				distance[t - 1] = distance[t] + 1
		if t < N - 1:
			if visited[t + 1] == 0:
				Q.put(t + 1)
				visited[t + 1] = 1
				distance[t + 1] = distance[t] + 1
		visited[t] = 1
	print(distance[-1])
else:
	print(0)


from sys import stdin, stdout
import math
from collections import defaultdict, deque

def bfs(d, n, d1, s):
	high = [-1 for x in range(n + 1)]
	q = deque([0])
	high[0] = 0
	while q:
		node = q.popleft()
		for x in d1[int(s[node])]:
			if high[x] == -1:
				high[x] = high[node] + 1
				q.append(x)
		for x in d[node]:
			if high[x] == -1:
				high[x] = high[node] + 1
				q.append(x)
	print(high[n])

def main():
	try:
		s = stdin.readline().strip()
		n = len(s)
		d = defaultdict(list)
		for i in range(1, len(s)):
			d[int(s[i])].append(i)
		high = [0] * (n + 1)
		visit = [False] * (n + 1)
		q = deque([0])
		while q:
			node = q.popleft()
			if node == n - 1:
				break
			for x in d[int(s[node])]:
				if visit[x] == False:
					visit[x] = True
					q.append(x)
					high[x] = high[node] + 1
			d[int(s[node])].clear()
			if node - 1 >= 0 and (not visit[node - 1]):
				visit[node - 1] = True
				q.append(node - 1)
				high[node - 1] = high[node] + 1
			if node + 1 < n and (not visit[node + 1]):
				visit[node + 1] = True
				q.append(node + 1)
				high[node + 1] = high[node] + 1
		print(high[n - 1])
	except:
		pass

def add(a, b, c):
	res = a + b
	if res >= c:
		return res - c
	else:
		return res

def mod(a, b, c):
	res = a * b
	if res >= c:
		return res % c
	else:
		return res

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def lcm(a, b):
	w = a // gcd(a, b)
	return w * b

def expo(a, b):
	(x, y) = (1, a)
	while b > 0:
		if b & 1:
			x = x * y
		y = y * y
		b >>= 1
	return x

def power(a, b, m):
	(x, y) = (1,)
	while b > 0:
		if b & 1:
			x = mod(x, y, m)
		y = mod(y, y, m)
		b >>= 1
	return x

def L():
	return list(map(int, stdin.readline().split()))

def In():
	return list(map(int, stdin.readline().split()))

def I():
	return int(stdin.readline())
P = 1000000007

def __starting_point():
	main()
__starting_point()


from sys import stdin, stdout

def sin():
	return stdin.readline().rstrip()

def listInput():
	return list(map(int, sin().split()))

def printBS(li):
	if not li:
		return
	for i in range(len(li) - 1):
		stdout.write('%d ' % li[i])
	stdout.write('%d\n' % li[-1])
li = [int(i) for i in sin()]
MAX = 10 ** 6
n = len(li)
mc = [MAX] * 10
ans = [MAX] * n
ans[-1] = 0
mc[li[-1]] = 0
for _ in range(19):
	for i in range(n - 2, -1, -1):
		ans[i] = min(ans[i + 1] + 1, 1 + mc[li[i]])
		if ans[i] < mc[li[i]]:
			mc[li[i]] = ans[i]
	for i in range(1, n - 1):
		ans[i] = min(ans[i - 1] + 1, 1 + mc[li[i]], ans[i])
		mc[li[i]] = min(ans[i], mc[li[i]])
print(ans[0])


from collections import defaultdict, deque
text = input().strip()
v = len(text)
g = defaultdict(list)
store = defaultdict(list)
for i in range(1, v):
	temp = ord(text[i]) - 48
	store[temp].append(i)
que = [0]
dist = [0] * v
vis = [False] * v
vis[0] = True
while len(que):
	index = que.pop(0)
	if index == v - 1:
		break
	temp = ord(text[index]) - 48
	for i in store[temp]:
		if not vis[i]:
			vis[i] = True
			que.append(i)
			dist[i] = dist[index] + 1
	del store[temp]
	left = index - 1
	right = index + 1
	if left >= 0 and (not vis[left]):
		vis[left] = True
		que.append(left)
		dist[left] = dist[index] + 1
	if right < v and (not vis[right]):
		vis[right] = True
		que.append(right)
		dist[right] = dist[index] + 1
print(dist[v - 1])


from heapq import *
S = input().strip()
N = len(S)
graph = [[] for i in range(N + 10)]
for i in range(N):
	if i == 0:
		graph[i].append((1, i + 1))
	elif i == N - 1:
		graph[i].append((1, i - 1))
	else:
		graph[i].append((1, i + 1))
		graph[i].append((1, i - 1))
	dummy_node = N + int(S[i])
	graph[i].append((0.5, dummy_node))
	graph[dummy_node].append((0.5, i))

def dijkstra(s):
	q = [(0, s)]
	dist[s] = 0
	while q:
		(d, u) = heappop(q)
		if d <= dist[u]:
			for (w, v) in graph[u]:
				if dist[v] > dist[u] + w:
					dist[v] = dist[u] + w
					heappush(q, (dist[v], v))
inf = 1 << 64 - 1
dist = [inf for _ in range(N + 10)]
dijkstra(0)
print(int(dist[N - 1]))


s = input().strip()
adj = [[] for _ in range(10)]
for i in range(len(s)):
	adj[int(s[i])].append(i)
d = [-1] * len(s)
d[0] = 0
queue = []
queue.append(0)
while queue:
	u = queue.pop(0)
	if d[len(s) - 1] != -1:
		break
	n = int(s[u])
	for v in adj[n]:
		if d[v] == -1:
			d[v] = d[u] + 1
			queue.append(v)
	adj[n] = []
	if u and d[u - 1] == -1:
		d[u - 1] = d[u] + 1
		queue.append(u - 1)
	if u + 1 < len(s) and d[u + 1] == -1:
		d[u + 1] = d[u] + 1
		queue.append(u + 1)
print(d[len(s) - 1])


import sys
from collections import deque
s = list(map(int, list(input().strip())))
n = len(s)
digits = [[] for i in range(10)]
dist = [-1] * n
used = [False] * 10
for i in range(n):
	digits[s[i]].append(i)
dist[0] = 0
q = deque([0])
ans = 0
while q:
	v = q.popleft()
	cur = dist[v]
	if v == n - 1:
		print(cur)
		sys.exit()
	if cur != 0 and dist[v - 1] == -1:
		dist[v - 1] = cur + 1
		q.append(v - 1)
	if dist[v + 1] == -1:
		dist[v + 1] = cur + 1
		q.append(v + 1)
	if not used[s[v]]:
		used[s[v]] = True
		for i in digits[s[v]]:
			if dist[i] == -1:
				dist[i] = cur + 1
				q.append(i)


import queue
MAX_N = 100005
MAX_DIGIT = 10
dist = [-1 for _ in range(MAX_N)]
position = [[] for _ in range(MAX_DIGIT)]
commands = input().strip()
n = len(commands)

def BFS(start, end, dist, position, n, commands):
	myqueue = queue.Queue()
	myqueue.put(start)
	dist[start] = 0
	while myqueue.qsize() > 0:
		u = myqueue.get()
		if u > 0 and dist[u - 1] == -1:
			dist[u - 1] = dist[u] + 1
			myqueue.put(u - 1)
		if u < n - 1 and dist[u + 1] == -1:
			dist[u + 1] = dist[u] + 1
			myqueue.put(u + 1)
		for v in position[ord(commands[u]) - 48]:
			if dist[v] == -1:
				dist[v] = dist[u] + 1
				myqueue.put(v)
		position[ord(commands[u]) - 48].clear()
	print(dist[end])
for i in range(n):
	position[ord(commands[i]) - 48].append(i)
BFS(0, n - 1, dist, position, n, commands)


import sys
import math
from collections import defaultdict
try:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
except:
	pass
s = input().strip()
at = {}
n = len(s)
at = defaultdict(list)
for i in range(n):
	at[int(s[i])].append(i)
visited = defaultdict(lambda : False)
dist = defaultdict(lambda : float('inf'))
visited[0] = True
dist[0] = 0
queue = [0]
added = {}
while queue:
	u = queue.pop(0)
	char = int(s[u])
	for v in at[char]:
		if not visited[v]:
			visited[v] = True
			queue.append(v)
			dist[v] = dist[u] + 1
	at[char] = []
	if u != 0:
		v = u - 1
		if not visited[v]:
			visited[v] = True
			queue.append(v)
			dist[v] = dist[u] + 1
	if u != n - 1:
		v = u + 1
		if not visited[v]:
			visited[v] = True
			queue.append(v)
			dist[v] = dist[u] + 1
print(dist[n - 1])


__author__ = 'Ronald Kaiser'
__email__ = 'raios dot catodicos at gmail dot com'
from math import inf
S = list(map(int, input().strip()))
a = [[] for i in range(10)]
[a[v].append(i) for (i, v) in enumerate(S)]
d = [False] * 10
m_l = [(False, inf)] * len(S)
m_l[0] = (True, 0)
q = [0]
while len(q):
	current = q.pop(0)
	if current == len(S) - 1:
		print(m_l[current][1])
		break
	for adj in [current - 1, current + 1]:
		if not 0 <= adj < len(S) or m_l[adj][0]:
			continue
		m_l[adj] = (True, m_l[current][1] + 1)
		q.append(adj)
	if d[S[current]] == False:
		d[S[current]] = True
		for p in a[S[current]]:
			if m_l[p][0] == True:
				continue
			m_l[p] = (True, m_l[current][1] + 1)
			q.append(p)


from sys import stdin, stdout
S = [int(z) for z in stdin.readline().strip()]
n = len(S)
graph = {}
d = {}
visited = {}
for i in range(n):
	graph[S[i]] = []
	visited[i] = 0
	d[i] = 0
if n > 1:
	for i in range(n):
		graph[S[i]].append(i)
	queue = [0]
	while len(queue) != 0:
		u = queue.pop(0)
		for v in graph[S[u]]:
			if visited[v] == 0 and v != u:
				d[v] += d[u] + 1
				queue.append(v)
				visited[v] = 1
		graph[S[u]] = []
		if u - 1 >= 0:
			if visited[u - 1] == 0:
				d[u - 1] = d[u] + 1
				visited[u - 1] = 1
				queue.append(u - 1)
		if u + 1 < n:
			if visited[u + 1] == 0:
				d[u + 1] = d[u] + 1
				visited[u + 1] = 1
				queue.append(u + 1)
		visited[u] = 1
	stdout.write('%d\n' % d[n - 1])
else:
	stdout.write('0\n')


from queue import Queue
s = input().strip()
neighbours = [[] for _ in range(10)]
for index_node in range(len(s)):
	value_node = int(s[index_node])
	neighbours[value_node].append(index_node)
distances = [-1] * len(s)
distances[0] = 0
q = Queue()
q.put(0)
while q.empty() == False:
	if distances[len(s) - 1] != -1:
		break
	current_node_index = q.get(0)
	value = int(s[current_node_index])
	for neighbour_index in neighbours[value]:
		if distances[neighbour_index] == -1:
			distances[neighbour_index] = distances[current_node_index] + 1
			q.put(neighbour_index)
	neighbours[value] = []
	if current_node_index + 1 < len(s) and distances[current_node_index + 1] == -1:
		distances[current_node_index + 1] = distances[current_node_index] + 1
		q.put(current_node_index + 1)
	if current_node_index - 1 > 0 and distances[current_node_index - 1] == -1:
		distances[current_node_index - 1] = distances[current_node_index] + 1
		q.put(current_node_index - 1)
print(distances[len(s) - 1])


from collections import defaultdict

class Graph:

	def __init__(self, v):
		self.adj = defaultdict(list)
		self.V = v

	def findstep(self, s):
		visit = [0] * self.V
		dist = [0] * self.V
		q = []
		q.append(0)
		while q:
			t = q.pop(0)
			visit[t] = 1
			for i in self.adj[s[t]]:
				if visit[i] == 0 and i != t:
					q.append(i)
					visit[i] = 1
					dist[i] = dist[t] + 1
			self.adj[s[t]] = []
			if t > 0 and visit[t - 1] == 0:
				q.append(t - 1)
				visit[t - 1] = 1
				dist[t - 1] = dist[t] + 1
			if t < self.V - 1 and visit[t + 1] == 0:
				q.append(t + 1)
				visit[t + 1] = 1
				dist[t + 1] = dist[t] + 1
		return dist[-1]
s = list(map(int, input().strip()))
n = len(s)
g = Graph(n)
for i in range(n):
	g.adj[s[i]].append(i)
print(g.findstep(s))


from collections import defaultdict

def main(string):
	(graph, visited) = (defaultdict(list), [False] * len(string))
	queue = [(string[0], 0, 0)]
	visited[0] = True
	for (index, character) in enumerate(string):
		graph[character].append(index)
	while queue:
		(number, index, distance) = queue.pop(0)
		if index == len(string) - 1:
			return distance
		if number in graph:
			for otherIndex in graph[number]:
				if not visited[otherIndex]:
					visited[otherIndex] = True
					queue.append((number, otherIndex, distance + 1))
			del graph[number]
		if index > 0 and (not visited[index - 1]):
			visited[index - 1] = True
			queue.append((string[index - 1], index - 1, distance + 1))
		if index < len(string) - 1 and (not visited[index + 1]):
			visited[index + 1] = True
			queue.append((string[index + 1], index + 1, distance + 1))
string = input().strip()
print(main(string))


s = input().strip()
N = len(s)
v = [-1] * N
e = [0] * 10
v[0] = 0
s1 = [0]
c = 0
while c < N:
	cur = s1[c]
	if e[int(s[cur])] == 0:
		for i in range(N):
			if v[i] < 0 and s[i] == s[cur]:
				v[i] = v[cur] + 1
				s1.append(i)
		e[int(s[cur])] = 1
	if cur > 0 and v[cur - 1] < 0:
		v[cur - 1] = v[cur] + 1
		s1.append(cur - 1)
	if cur < N - 1 and v[cur + 1] < 0:
		v[cur + 1] = v[cur] + 1
		s1.append(cur + 1)
	c = c + 1
print(v[-1])


import queue

def BFS(start, end, dist, adj, s):
	vis = queue.Queue()
	vis.put(start)
	dist[start] = 0
	while vis.qsize() > 0:
		ind = vis.get()
		if ind > 0 and dist[ind - 1] == -1:
			dist[ind - 1] = dist[ind] + 1
			vis.put(ind - 1)
		if ind < len(s) - 1 and dist[ind + 1] == -1:
			dist[ind + 1] = dist[ind] + 1
			vis.put(ind + 1)
		for v in adj[s[ind]]:
			if dist[v] == -1:
				dist[v] = dist[ind] + 1
				vis.put(v)
		adj[s[ind]].clear()
	return dist[end]
s = [int(x) for x in input().strip()]
N = len(s)
dist = [-1 for _ in range(N)]
adj = [[] for _ in range(10)]
for i in range(N):
	adj[s[i]].append(i)
print(BFS(0, N - 1, dist, adj, s))


seq = [int(x) for x in input().strip()]
n = len(seq)
if n == 1:
	print(0)
elif n == 2:
	print(1)
else:
	same = [[] for _ in range(10)]
	cost_arr = [0.5 for _ in range(n)]
	bool_arr = [False for _ in range(10)]
	for index in range(n):
		same[seq[index]].append(index)
	cost_arr[n - 1] = 0
	mark_list = [n - 1]
	k = 1
	while cost_arr[0] == 0.5 and len(mark_list) != 0:
		local_list = []
		for index in mark_list:
			num = seq[index]
			if index + 1 < n and cost_arr[index + 1] == 0.5:
				cost_arr[index + 1] = k
				local_list.append(index + 1)
			if index > 0 and cost_arr[index - 1] == 0.5:
				cost_arr[index - 1] = k
				local_list.append(index - 1)
			if not bool_arr[num]:
				for duplicate in same[num]:
					if cost_arr[duplicate] == 0.5:
						cost_arr[duplicate] = cost_arr[index] + 1
						local_list.append(duplicate)
				bool_arr[num] = True
		mark_list = local_list
		k += 1
	print(cost_arr[0])


__author__ = 'Ronald Kaiser'
__email__ = 'raios dot catodicos at gmail dot com'
from math import inf
S = list(map(int, input().strip()))
a = [[] for i in range(10)]
[a[v].append(i) for (i, v) in enumerate(S) if i != v]
d = [False] * 10
m = [False] * len(S)
m[0] = 1
l = [inf] * len(S)
l[0] = 0
q = [0]
while len(q):
	current = q.pop(0)
	if current == len(S) - 1:
		print(l[current])
		break
	adjs = list(filter(lambda x: 0 <= x < len(S) and (not m[x]), [current - 1, current + 1]))
	for adj in adjs:
		m[adj] = True
		l[adj] = l[current] + 1
	q.extend(adjs)
	if d[S[current]] == False:
		d[S[current]] = True
		for p in a[S[current]]:
			if m[p] == True:
				continue
			m[p] = True
			l[p] = l[current] + 1
			q.append(p)


from collections import defaultdict
s = input().strip()
size = len(s)
ans = defaultdict(list)
for i in range(size):
	ans[s[i]].append(i)
queue = [0]
visited = {0: 0}
while queue:
	temp = queue.pop(0)
	if temp == size - 1:
		break
	length = len(ans[s[temp]])
	for i in range(length):
		if ans[s[temp]][i] not in visited:
			visited[ans[s[temp]][i]] = visited[temp] + 1
			queue.append(ans[s[temp]][i])
	ans[s[temp]] = []
	if temp + 1 not in visited and temp + 1 < size:
		queue.append(temp + 1)
		visited[temp + 1] = visited[temp] + 1
	if temp - 1 not in visited and temp - 1 >= 0:
		queue.append(temp - 1)
		visited[temp - 1] = visited[temp] + 1
print(visited[size - 1])


N = input().strip()
length = len(N)
pi = [-1] * length
ni = [0] * 10
pi[0] = 0
id = 0
cr = [0]
c = 0
while c < length:
	numtmp = cr[c]
	if ni[int(N[numtmp])] == 0:
		for i in range(length):
			if pi[i] < 0 and N[i] == N[numtmp]:
				pi[i] = pi[numtmp] + 1
				cr.append(i)
		ni[int(N[numtmp])] = 1
	if numtmp > 0 and pi[numtmp - 1] < 0:
		pi[numtmp - 1] = pi[numtmp] + 1
		cr.append(numtmp - 1)
	if numtmp < length - 1 and pi[numtmp + 1] < 0:
		pi[numtmp + 1] = pi[numtmp] + 1
		cr.append(numtmp + 1)
	c = c + 1
print(pi[-1])


s1 = input()
s1 = s1.strip()
s1 = list(s1)
s = []
hash1 = []
for i in range(10):
	hash1.append([])
l = len(s1)
for i in range(l):
	s.append(int(s1[i]))
	hash1[s[i]].append(i)
src = 0
dest = l - 1
if l == 1:
	print(0)
else:
	dist = []
	visited = []
	times = []
	for i in range(l):
		dist.append(0)
		visited.append(0)
	dist[0] = 0
	qu = []
	le = 0
	qu.append(0)
	le += 1
	visited[0] = 1
	while le != 0:
		x = qu[0]
		del qu[0]
		le -= 1
		if x == l - 1:
			break
		if x - 1 >= 0 and visited[x - 1] == 0:
			visited[x - 1] = 1
			qu.append(x - 1)
			le += 1
			dist[x - 1] = dist[x] + 1
		if x + 1 < l and visited[x + 1] == 0:
			visited[x + 1] = 1
			qu.append(x + 1)
			le += 1
			dist[x + 1] = dist[x] + 1
		for i in range(len(hash1[s[x]])):
			if visited[hash1[s[x]][i]] == 0:
				visited[hash1[s[x]][i]] = 1
				qu.append(hash1[s[x]][i])
				dist[hash1[s[x]][i]] = dist[x] + 1
				le += 1
		hash1[s[x]] = []
	print(dist[l - 1])


inn = input().strip()
queue = []
check = 0
n = len(inn)
idex = [[] for _ in range(10)]
jump = [-1 for _ in range(n)]
jump[0] = 0
queue = [0]
if len(inn) == 1:
	print(0)
else:
	for i in range(n):
		nn = int(inn[i])
		idex[nn].append(i)
	while jump[-1] == -1:
		idx = queue.pop(0)
		v = int(inn[idx])
		left = idx - 1
		rigth = idx + 1
		if left > 0:
			if jump[left] == -1:
				jump[left] = jump[idx] + 1
				queue.append(left)
		if rigth < n:
			if jump[rigth] == -1:
				jump[rigth] = jump[idx] + 1
				queue.append(rigth)
		if len(idex[v]) > 0:
			idex[v].remove(idx)
			for i in idex[v][::-1]:
				if jump[-1] != -1:
					break
				if jump[i] == -1:
					jump[i] = jump[idx] + 1
					queue.append(i)
			idex[v] = []
	print(jump[-1])


n = input().strip()
l = len(n)
p = [-1] * l
u = [0] * 10
p[0] = 0
id = 0
c1 = [0]
c2 = 0
while c2 < l:
	n2 = c1[c2]
	if u[int(n[n2])] == 0:
		for j in range(l):
			if p[j] < 0 and n[j] == n[n2]:
				p[j] = p[n2] + 1
				c1.append(j)
		u[int(n[n2])] = 1
	if n2 > 0 and p[n2 - 1] < 0:
		p[n2 - 1] = p[n2] + 1
		c1.append(n2 - 1)
	if n2 < l - 1 and p[n2 + 1] < 0:
		p[n2 + 1] = p[n2] + 1
		c1.append(n2 + 1)
	c2 += 1
print(p[-1])


digit = {'0': [], '1': [], '2': [], '3': [], '4': [], '5': [], '6': [], '7': [], '8': [], '9': []}
s = input().strip()
slen = len(s)
depth = []
visited = []
queuee = []
for i in range(slen):
	digit[s[i]].append(i)
	depth.append(0)
	visited.append(False)
depth[0] = 0
visited[0] = True
queuee.append(0)
while len(queuee):
	index = queuee.pop(0)
	if index == slen - 1:
		break
	for i in digit[s[index]]:
		if not visited[i]:
			visited[i] = True
			queuee.append(i)
			depth[i] = depth[index] + 1
	digit[s[index]] = []
	if index - 1 >= 0 and (not visited[index - 1]):
		visited[index - 1] = True
		queuee.append(index - 1)
		depth[index - 1] = depth[index] + 1
	if index + 1 < slen and (not visited[index + 1]):
		visited[index + 1] = True
		queuee.append(index + 1)
		depth[index + 1] = depth[index] + 1
print(depth[slen - 1])


import queue
n = input().strip()
a = []
l = 0
for i in n:
	a.append(int(i))
	l += 1
check = [[0] for x in range(10)]
for i in range(l):
	check[a[i]].append(i)
q = queue.Queue(l + 1)
visited = [-1 for x in range(l)]
q.put(0)
visited[0] = 0
while q.empty() == False:
	cur = q.get()
	if cur - 1 >= 0 and visited[cur - 1] == -1:
		q.put(cur - 1)
		visited[cur - 1] = visited[cur] + 1
	if cur + 1 < l and visited[cur + 1] == -1:
		q.put(cur + 1)
		visited[cur + 1] = visited[cur] + 1
	if check[a[cur]][0] == 0:
		check[a[cur]][0] = 1
		for i in range(1, len(check[a[cur]])):
			if visited[check[a[cur]][i]] == -1:
				q.put(check[a[cur]][i])
				visited[check[a[cur]][i]] = visited[cur] + 1
				if check[a[cur]][i] == l - 1:
					break
	if visited[l - 1] != -1:
		break
print(visited[l - 1])


import sys
import math
from collections import defaultdict
try:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
except:
	pass

class Graph:

	def __init__(self):
		self.neighbours = defaultdict(set)

	def addEdge(self, u, v):
		if v not in self.neighbours[u]:
			self.neighbours[u].add(v)
			self.neighbours[v].add(u)

	def BFS(self, n, s, at):
		visited = defaultdict(lambda : False)
		dist = defaultdict(lambda : float('inf'))
		visited[0] = True
		dist[0] = 0
		queue = [0]
		added = {}
		while queue:
			u = queue.pop(0)
			char = s[u]
			if char not in added:
				added[char] = True
				for idx in at[char]:
					g.addEdge(u, idx)
			for v in self.neighbours[u]:
				if not visited[v]:
					visited[v] = True
					queue.append(v)
					dist[v] = dist[u] + 1
		return dist[n - 1]
s = input().strip()
at = {}
n = len(s)
g = Graph()
at = defaultdict(list)
for i in range(n):
	at[s[i]].append(i)
for i in range(1, n):
	g.addEdge(i - 1, i)
for i in range(n - 1):
	g.addEdge(i, i + 1)
print(g.BFS(n, s, at))


seq = [int(x) for x in input().strip()]
n = len(seq)
if n == 1:
	print(0)
elif n == 2:
	print(1)
else:
	arr = list()
	same = [[] for _ in range(10)]
	cost_arr = [0 for _ in range(n)]
	bool_arr = [False for _ in range(10)]
	for j in range(n):
		same[seq[j]].append(j)
	cost_arr[0] = 1
	arr.append(0)
	while cost_arr[n - 1] == 0 and len(arr) != 0:
		index = arr.pop(0)
		num = seq[index]
		if not bool_arr[num]:
			size = len(same[num])
			for i in range(size):
				if cost_arr[same[num][i]] == 0:
					cost_arr[same[num][i]] = cost_arr[index] + 1
					arr.append(same[num][i])
			bool_arr[num] = True
		if index > 0 and cost_arr[index - 1] == 0:
			cost_arr[index - 1] = cost_arr[index] + 1
			arr.append(index - 1)
		if index + 1 < n and cost_arr[index + 1] == 0:
			cost_arr[index + 1] = cost_arr[index] + 1
			arr.append(index + 1)
	print(cost_arr[n - 1] - 1)


from collections import defaultdict
s = input().strip()
n = len(s)
indices = defaultdict(list)
for i in range(n):
	indices[int(s[i])].append(i)
q = []
dist = [-1 for i in range(n)]
q.append(0)
dist[0] = 0
while q:
	u = q.pop(0)
	if u - 1 >= 0 and dist[u - 1] == -1:
		q.append(u - 1)
		dist[u - 1] = 1 + dist[u]
	if u + 1 < n and dist[u + 1] == -1:
		q.append(u + 1)
		dist[u + 1] = 1 + dist[u]
	for v in indices[int(s[u])]:
		if dist[v] == -1:
			dist[v] = 1 + dist[u]
			q.append(v)
	indices[int(s[u])] = []
print(dist[n - 1])


N = input().strip()
length = len(N)
pi = [-1] * length
ni = [0] * 10
pi[0] = 0
id = 0
current = [0]
counter = 0
while counter < length:
	np = current[counter]
	if ni[int(N[np])] == 0:
		for i in range(length):
			if pi[i] < 0 and N[i] == N[np]:
				pi[i] = pi[np] + 1
				current.append(i)
		ni[int(N[np])] = 1
	if np > 0 and pi[np - 1] < 0:
		pi[np - 1] = pi[np] + 1
		current.append(np - 1)
	if np < length - 1 and pi[np + 1] < 0:
		pi[np + 1] = pi[np] + 1
		current.append(np + 1)
	counter = counter + 1
print(pi[-1])


from queue import Queue
import sys
sys.setrecursionlimit(100000)
MAX = 100000
path = [0 for i in range(MAX)]
visited = [False for i in range(MAX)]
graph = [[] for i in range(10)]

def BFS(start, end):
	q = Queue()
	q.put(start)
	visited[start] = True
	while not q.empty():
		u = q.get()
		if u == end:
			break
		tmp = ord(s[u]) - 48
		for i in range(len(graph[tmp])):
			v = graph[tmp][i]
			if not visited[v]:
				visited[v] = True
				path[v] = path[u] + 1
				q.put(v)
		graph[tmp].clear()
		if u - 1 >= 0 and (not visited[u - 1]):
			visited[u - 1] = True
			path[u - 1] = path[u] + 1
			q.put(u - 1)
		if u + 1 < n and (not visited[u + 1]):
			visited[u + 1] = True
			path[u + 1] = path[u] + 1
			q.put(u + 1)
	return path[end]
s = input().strip()
n = len(s)
for i in range(n):
	tmp = ord(s[i]) - 48
	graph[tmp].append(i)
print(BFS(0, n - 1))


from collections import defaultdict as dd
s = input().strip()
n = len(s)
vis = [False for i in range(n)]
d = [False for i in range(n)]
V = dd(list)
for i in range(1, n):
	val = ord(s[i]) - 48
	V[val].append(i)
d[0] = 0
vis[0] = True
Q = []
Q.append(0)
while len(Q):
	idx = Q[0]
	if idx == n - 1:
		break
	Q.pop(0)
	val = ord(s[idx]) - 48
	vsz = len(V[val])
	for j in range(vsz):
		nidx = V[val][j]
		if not vis[nidx]:
			vis[nidx] = True
			Q.append(nidx)
			d[nidx] = d[idx] + 1
	V[val].clear()
	if idx - 1 >= 0 and (not vis[idx - 1]):
		vis[idx - 1] = True
		Q.append(idx - 1)
		d[idx - 1] = d[idx] + 1
	if idx + 1 < n and (not vis[idx + 1]):
		vis[idx + 1] = True
		Q.append(idx + 1)
		d[idx + 1] = d[idx] + 1
print(d[n - 1])


N = input().strip()
length = len(N)
positioni = [-1] * length
numberi = [0] * 10
positioni[0] = 0
id = 0
cr = [0]
count = 0
while count < length:
	ntmp = cr[count]
	if numberi[int(N[ntmp])] == 0:
		for i in range(length):
			if positioni[i] < 0 and N[i] == N[ntmp]:
				positioni[i] = positioni[ntmp] + 1
				cr.append(i)
		numberi[int(N[ntmp])] = 1
	if ntmp > 0 and positioni[ntmp - 1] < 0:
		positioni[ntmp - 1] = positioni[ntmp] + 1
		cr.append(ntmp - 1)
	if ntmp < length - 1 and positioni[ntmp + 1] < 0:
		positioni[ntmp + 1] = positioni[ntmp] + 1
		cr.append(ntmp + 1)
	count = count + 1
print(positioni[-1])


import re
from collections import deque
QUEUED = set()
NEXT = deque([])
USED_DIGITS = set()
JUMPS = {}

def get_steps():
	steps = 0
	index = 0
	end = len(S) - 1
	for i in range(0, 10):
		JUMPS[str(i)] = []
	for (i, digit) in enumerate(S):
		JUMPS[digit].append(i)
	while index != end:
		if S[index] not in USED_DIGITS:
			for i in reversed(JUMPS[S[index]]):
				if i != index and i not in QUEUED:
					if i == end:
						NEXT.append((i, steps + 1))
						QUEUED.add(i)
					elif S[i + 1] not in USED_DIGITS or S[i - 1] not in USED_DIGITS:
						NEXT.append((i, steps + 1))
						QUEUED.add(i)
			USED_DIGITS.add(S[index])
		if index + 1 not in QUEUED and S[index + 1] not in USED_DIGITS:
			NEXT.append((index + 1, steps + 1))
			QUEUED.add(i)
		if index - 1 not in QUEUED and S[index - 1] not in USED_DIGITS and index:
			NEXT.append((index - 1, steps + 1))
			QUEUED.add(i)
		USED_DIGITS.add(S[index])
		(index, steps) = NEXT.popleft()
	return steps
S = input()
S = re.sub('\\D', '', S)
S = re.sub('(\\d)\\1\\1+', '\\1\\1', S)
print(get_steps())


from collections import deque
seq = [int(x) for x in list(input()) if x.isdigit()]
pos = [[] for _ in range(10)]
for (i, e) in enumerate(seq):
	pos[e].append(i)
dist = [-1] * len(seq)
dist[0] = 0
Q = deque([0])
while Q:
	i = Q.popleft()
	if i > 0 and dist[i - 1] == -1:
		dist[i - 1] = dist[i] + 1
		Q.append(i - 1)
	if i + 1 < len(seq) and dist[i + 1] == -1:
		dist[i + 1] = dist[i] + 1
		Q.append(i + 1)
	for j in pos[seq[i]]:
		if dist[j] != -1:
			continue
		dist[j] = dist[i] + 1
		Q.append(j)
	pos[seq[i]].clear()
print(dist[-1])


from collections import deque
s = [int(x) for x in input().strip()]
N = len(s)
(dist, a) = ([-1 for _ in range(N)], [[] for _ in range(10)])
for i in range(N):
	a[s[i]].append(i)
seen = deque([0])
dist[0] = 0
while seen:
	idx = seen.popleft()
	if idx > 0 and dist[idx - 1] == -1:
		dist[idx - 1] = dist[idx] + 1
		seen.append(idx - 1)
	if idx < len(s) - 1 and dist[idx + 1] == -1:
		dist[idx + 1] = dist[idx] + 1
		seen.append(idx + 1)
	for v in a[s[idx]]:
		if dist[v] == -1:
			dist[v] = dist[idx] + 1
			seen.append(v)
	a[s[idx]].clear()
print(dist[-1])


import queue
MAX_N = 100010
MAX_DIGIT = 10

def BFS(start, end, dist, position, sequence):
	visited = queue.Queue()
	visited.put(start)
	dist[start] = 0
	while visited.qsize() > 0:
		currentNode = visited.get()
		if currentNode > 0 and dist[currentNode - 1] == -1:
			dist[currentNode - 1] = dist[currentNode] + 1
			visited.put(currentNode - 1)
		if currentNode < len(sequence) - 1 and dist[currentNode + 1] == -1:
			dist[currentNode + 1] = dist[currentNode] + 1
			visited.put(currentNode + 1)
		for v in position[sequence[currentNode]]:
			if dist[v] == -1:
				dist[v] = dist[currentNode] + 1
				visited.put(v)
		position[sequence[currentNode]].clear()
	return dist[end]
sequence = [int(x) for x in input().strip()]
N = len(sequence)
dist = [-1 for _ in range(N)]
position = [[] for _ in range(MAX_DIGIT)]
for i in range(N):
	position[sequence[i]].append(i)
print(BFS(0, N - 1, dist, position, sequence))


import sys
import queue
sys.setrecursionlimit(100000)
INF = int(10000000.0 + 1)
MAX = 100005

class Pair:

	def __init__(self, a, b):
		self.first = a
		self.second = b

def minJumps(s):
	s = list(map(int, list(s)))
	occ = [[] for i in range(10)]
	for i in range(len(s)):
		occ[s[i]].append(i)
	vis = [False for i in range(len(s))]
	Q = queue.Queue()
	Q.put(Pair(0, 0))
	vis[0] = True
	ans = -1
	while not Q.empty():
		front = Q.get()
		(u, w) = (front.first, front.second)
		if u == len(s) - 1:
			ans = w
			break
		if u < len(s) - 1 and (not vis[u + 1]):
			Q.put(Pair(u + 1, w + 1))
			vis[u + 1] = True
		if u > 0 and (not vis[u - 1]):
			Q.put(Pair(u - 1, w + 1))
			vis[u - 1] = False
		for idx in occ[s[u]]:
			if not vis[idx]:
				vis[idx] = True
				Q.put(Pair(idx, w + 1))
		occ[s[u]].clear()
	print(ans)

def main():
	minJumps(input().strip())
main()


from queue import Queue
s = input().strip()
edges = [[] for _ in range(10)]
for i in range(len(s)):
	edges[int(s[i])].append(i)
dist = [-1 for _ in range(len(s))]
q = Queue()
q.put(0)
dist[0] = 0
while not q.empty():
	index = q.get()
	if dist[len(s) - 1] != -1:
		break
	val = int(s[index])
	for v in edges[val]:
		if dist[v] == -1:
			dist[v] = dist[index] + 1
			q.put(v)
	edges[val] = []
	if index > 0 and dist[index - 1] == -1:
		dist[index - 1] = dist[index] + 1
		q.put(index - 1)
	if index + 1 < len(s) and dist[index + 1] == -1:
		dist[index + 1] = dist[index] + 1
		q.put(index + 1)
print(dist[len(s) - 1])


import heapq
import sys

def main(raw_sequence: str) -> int:
	if len(raw_sequence) == 1:
		return 0
	elif raw_sequence[0] == raw_sequence[-1]:
		return 1
	sequence = [int(num) for num in raw_sequence]
	same_digit_indexes = [[] for _ in range(10)]
	digit_in_queue = [False] * len(sequence)
	queue = [(0, 0)]
	for (idx, digit) in enumerate(sequence):
		same_digit_indexes[digit].append(idx)
	while queue:
		(distance, idx) = heapq.heappop(queue)
		if idx == len(sequence) - 1:
			return distance
		digit = sequence[idx]
		candidates = [idx - 1, idx + 1]
		if same_digit_indexes[digit]:
			candidates.extend(same_digit_indexes[digit])
			same_digit_indexes[digit].clear()
		for candidate_idx in candidates:
			if candidate_idx <= 0 or candidate_idx >= len(sequence) or digit_in_queue[candidate_idx]:
				continue
			heapq.heappush(queue, (distance + 1, candidate_idx))
			digit_in_queue[candidate_idx] = True
for case in sys.stdin:
	print(main(case.strip()))