Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N, V, U = list(map(int, sys.stdin.buffer.readline().split()))
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N - 1)]

if V == U:
    print(0)
    exit()

V -= 1
U -= 1
graph = [[] for _ in range(N)]
for a, b in AB:
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

# 深い方に逃げるべき
# 子どものうち一番深い場所の深さ
children_depths = [-1 for _ in range(N)]
parents = [None for _ in range(N)]

stack = [(U, None)]
while stack:
    v, parent = stack.pop()
    parents[v] = parent
    for u in graph[v]:
        if u == parent:
            continue
        stack.append((u, v))

v = V
dist = 1
while parents[v] != U:
    v = parents[v]
    dist += 1

stack = []
for v in range(N):
    if len(graph[v]) == 1:
        stack.append((v, 0))
while stack:
    v, depth = stack.pop()
    if v == None:
        continue
    children_depths[v] = max(children_depths[v], depth)
    stack.append((parents[v], depth + 1))

# 何回親側に上がるか
p_cnt = 0
v = V
ans = 0
while dist > 0:
    ans = max(ans, dist - 1 + children_depths[v] + p_cnt)
    v = parents[v]
    p_cnt += 1
    dist -= 2
print(ans)


### FIXED CODE ###

import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N, V, U = list(map(int, sys.stdin.buffer.readline().split()))
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N - 1)]

V -= 1
U -= 1
graph = [[] for _ in range(N)]
for a, b in AB:
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

# 深い方に逃げるべき
# 子どものうち一番深い場所の深さ
children_depths = [0] * N
parents = [None] * N

stack = [(U, None)]
vs = []
while stack:
    v, parent = stack.pop()
    parents[v] = parent
    vs.append(v)
    for u in graph[v]:
        if u == parent:
            continue
        stack.append((u, v))
vs.reverse()
for v in vs:
    if parents[v] is not None:
        children_depths[parents[v]] = max(children_depths[parents[v]], children_depths[v] + 1)

v = V
dist = 1
while parents[v] != U:
    v = parents[v]
    dist += 1

# 何回親側に上がるか
p_cnt = 0
v = V
ans = 0
while dist > 0:
    ans = max(ans, dist - 1 + children_depths[v] + p_cnt)
    v = parents[v]
    p_cnt += 1
    dist -= 2
print(ans)
### BUGGY CODE ###

S = input()
mod = 10**9+7

N = len(S)
A1,A2,A3,C1,C2,C3 = [1]*N,[0]*N,[1]*N,[1]*N,[0]*N,[1]*N
A4,C4 = [1]*N,[1]*N
a,aa = 0,0
c,cc = 0,0
for i in range(1,N):
    if S[i-1]=="A":
        a += 1
    if S[i-1]=="?":
        aa += 1
        A3[i] = A3[i-1]*3
    else:
        A3[i] = A3[i-1]
    A1[i],A2[i] = a,aa
    A4[i] = A3[i]//3 % mod
for i in range(1,N):
    if S[N-1-i+1]=="C":
        c += 1
    if S[N-1-i+1]=="?":
        cc += 1
        C3[N-1-i] = C3[N-1-i+1]*3
    else:
        C3[N-1-i] = C3[N-1-i+1]
    C1[N-1-i] = c
    C2[N-1-i] = cc
    C4[N-1-i] = C3[N-1-i]//3 % mod

Ans = 0
for i in range(1,N-1):
    if S[i]=="B" or S[i]=="?":
        ta,tc = 0,0
        if A2[i]==0:
            ta = A1[i]
        else:
            ta = (A4[i]*(A1[i]*3 + A2[i])) % mod 
        if C2[i]==0:
            tc = C1[i]
        else:
            tc = (C4[i]*(C1[i]*3 + C2[i])) % mod
        Ans += ta*tc
        Ans

print(Ans % mod)

### FIXED CODE ###

S = input()
mod = 10**9+7

N = len(S)
A1,A2,C1,C2 = [1]*N,[1]*N,[1]*N,[1]*N
a,aa = 0,0
c,cc = 0,0
for i in range(1,N):
    if S[i-1]=="A":
        a += 1
    elif S[i-1]=="?":
        aa += 1
    A1[i],A2[i] = a,aa
for i in range(1,N):
    if S[N-1-i+1]=="C":
        c += 1
    elif S[N-1-i+1]=="?":
        cc += 1
    C1[N-1-i] = c
    C2[N-1-i] = cc

Ans = 0
for i in range(1,N-1):
    if S[i] in ("B","?"):
        ta,tc = 0,0
        if A2[i]==0:
            ta = A1[i]
        else:
            ta = pow(3,A2[i],mod)*A1[i] + pow(3,A2[i]-1,mod)*A2[i]
        if C2[i]==0:
            tc = C1[i]
        else:
            tc = pow(3,C2[i],mod)*C1[i] + pow(3,C2[i]-1,mod)*C2[i]
        Ans += ta*tc
        Ans %= mod

print(Ans)
### BUGGY CODE ###

import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

N = int(input())
A = list(map(int, input().split()))

cons = []
cur = 0
mn, mx = 0, 0
for i in range(N, -1, -1):
    mn = ((mn + 1) // 2) + A[i]
    mx = mx + A[i]
    if mn > 2 ** i:
        print(-1)
        exit()
    cons.append((mn, mx))
cons = list(reversed(cons))
ans = 0
cnt_node = 1
for i in range(N + 1):
    mn, mx = cons[i]
    now = min(mx, cnt_node)
    ans += now
    cnt_node = (now - A[i]) * 2
print(ans)



### FIXED CODE ###

import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

N = int(input())
A = list(map(int, input().split()))

cons = []
cur = 0
mn, mx = 0, 0
for i in range(N, -1, -1):
    mn = ((mn + 1) // 2) + A[i]
    mx = mx + A[i]
    if mn > 2 ** i:
        print(-1)
        exit()
    cons.append((mn, mx))
cons = list(reversed(cons))
ans = 0
cnt_node = 1
for i in range(N + 1):
    mn, mx = cons[i]
    now = min(mx, cnt_node)
    ans += now
    cnt_node = (now - A[i]) * 2
print(ans)
### BUGGY CODE ###

from sys import stdin
import sys

sys.setrecursionlimit(10**5)

class DFS():
    def __init__(self,A_B_arr,N,M):
        self.N = N
        self.M = M
        self.route = {i:[] for i in range(N+1)}
        for A, B in A_B_arr:
            self.route[A].append(B)
            self.route[B].append(A)

        self.dp = [[None,N] for i in range(N+1)]
        self.dp[1] = [1,0]

    def dfs(self,i,rank):
        for r in self.route[i]:
            if rank<self.dp[r][1] and rank<self.N:
                self.dp[r] = [i,rank]
                self.dfs(r,rank+1)
        return


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, M = list(map(int,_in[0].split(' ')))  # type:list(int)
    A_B_arr = []
    for i in range(M):
        _ = list(map(int,_in[i+1].split(' ')))  # type:list(int)
        A_B_arr.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    dfs = DFS(A_B_arr,N,M)
    dfs.dfs(1,1)

    ans = []
    TF = 'Yes'
    for (i,_) in enumerate(dfs.dp):
        if i>1:
            if _[0] == None:
                TF = 'No'
                break
            else:
                ans.append(_[0])
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    if TF == 'Yes':
        print(TF)
        for _ in ans:
            print(_)
    else:
        print(TF)


### FIXED CODE ###

from sys import stdin
from collections import deque


class BFS():
    def __init__(self, con, val=None):
        # 隣接リスト表現
        self.con = con
        self.val = val
        self.N = len(self.con)
        # 1つ前の部屋(1-indexed)
        self.dist = [-1]*self.N
        self.que = deque()

        # 初期条件(0-indexed)
        self.dist[0] = 0
        self.que.append(0)

    def bfs(self):
        while self.que:
            v = self.que.popleft()
            for next_v in self.con[v]:
                if self.dist[next_v] != -1:
                    continue
                self.dist[next_v] = v+1
                self.que.append(next_v)


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, M = list(map(int,_in[0].split(' ')))  # type:list(int)
    A_B_arr = []
    for i in range(M):
        _ = list(map(int,_in[i+1].split(' ')))  # type:list(int)
        A_B_arr.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    con = [[] for i in range(N)]
    for A,B in A_B_arr:
        A -= 1
        B -= 1
        con[A].append(B)
        con[B].append(A)

    bfs = BFS(con)
    bfs.bfs()
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    if -1 in bfs.dist[1:]:
        print('No')
    else:
        print('Yes')
        for _ in bfs.dist[1:]:
            print(_)
### BUGGY CODE ###

n = int(input())
x = [int(i) for i in input().split()]

for i in range(n):
    y = x[:i] + x[i+1:]
    y.sort()
    print(y[n//2-1])

### FIXED CODE ###

n = int(input())
x = [int(i) for i in input().split()]
y = sorted(x)
a , b = y[n//2-1], y[n//2]
for i in x:
    if i > a:
        print(a)
    else:
        print(b)
### BUGGY CODE ###

s = input()
q = int(input())

for i in range(q):
    L = list(input().split())
    if L[0] == '1' :
        s = ''.join(reversed(s))
    if L[0] == '2' :
        if L[1] == '1' :
            s = L[2] + s
        if L[1] == '2' :
            s = s + L[2]
print(s)
        

### FIXED CODE ###


from collections import deque

s = deque(list(input()))
q = int(input())
head = 0

for i in range(q):
    L = list(input().split())
    if L[0] == '1' :
        head = (head + 1)%2
    if L[0] == '2' :
        if head == 0:
            if L[1] == '1' :
                s.appendleft(L[2])
            if L[1] == '2' :
                s.append(L[2])
        if head == 1:
            if L[1] == '1' :
                s.append(L[2])
            if L[1] == '2' :
                s.appendleft(L[2])
if head == 0:
    print(''.join(s))
else: 
    print(''.join(reversed(s)))
### BUGGY CODE ###

n, k = map(int, input().split())

K = [int(i) for i in range(k, n + 2)]
#print(K)
N = [int(i) for i in range(n + 1)]
#print(N)
c = 0
for i in K:
  #print(N[: i])
  mi = sum(N[: i])
  ma = sum(N[::-1][: i])
  c += (ma - mi + 1)
  c %= (10 ** 9 + 7)
print(c)  

### FIXED CODE ###

n, k = map(int, input().split())

c = 0
for i in range(k, n + 2):
  c += ((n - i + 1) * i + 1) % (10 ** 9 + 7)

print(c % (10 ** 9 + 7))
### BUGGY CODE ###

n = int(input())

ans = set()
s = []


for i in range(n):
    s = [(input())]
    ans = ans ^ set(s)

print(len(ans))


### FIXED CODE ###

n = int(input())

ans = [input() for i in range(n)]

ans.sort()

s = sorted(set(ans))
t = 0
cnt = 0

result = 0
for i in range(n):
    temp = s[t]
    if ans[i] == temp:
        cnt += 1
    else:
        if cnt % 2 == 1:
            result += 1
        cnt = 1
        t += 1
else:
    if cnt % 2 == 1:
        result += 1
        
    
    

print(result)
### BUGGY CODE ###

import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)

N = I()
color = []
a = int(input())
maxcolor =[]
maxcolor.append(a)
lena = 1
for i in range(N-1):
    a = int(input())
    if a<=min(maxcolor):
        maxcolor.append(a)
        lena += 1
    else:
        aupper = lena-1
        alower = int(0)
        acandi = aupper//2
        while (True):
            if maxcolor[acandi]>=a:
                alower = acandi
                acandi = (aupper+acandi+1)//2
            else:
                if aupper - alower <= 1:
                    maxcolor[acandi] = a
                    break
                else:
                    aupper = acandi
                    acandi = (acandi + alower) // 2


#print(maxcolor)
ans = len(maxcolor)
print(ans)

### FIXED CODE ###

from collections import deque
import bisect
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
ans = int(0)

N = I()
color = []
a = I()
maxcolor =deque()
maxcolor.append(a)
lena = 1
for i in range(N-1):
    minmaxcolor = maxcolor[0]
    a = I()
    if a<=minmaxcolor:
        maxcolor.appendleft(a)
#        maxcolor.append(a)
        lena += 1
    else:
        acandi = bisect.bisect_left(maxcolor, a)
        maxcolor[acandi-1] = a
        """
        aupper = lena-1
        alower = int(0)
        acandi = aupper//2
        
        for _ in range(aupper+1):
            if maxcolor[acandi]>=a:
                alower = acandi
                acandi = (aupper+acandi+1)//2
            else:
                if aupper - alower <= 1:
                    maxcolor[acandi] = a
                    break
                else:
                    aupper = acandi
                    acandi = (acandi + alower) // 2
        """

#print(maxcolor)
ans = len(maxcolor)
print(ans)
### BUGGY CODE ###

S = str(input())
count = 0;
for i in range(100000):
  count=count+S.count('BW');
  S = S.replace('BW','WB');
  if 'BW' not in S:break;
print(count)


### FIXED CODE ###

S = input()
ans = 0
tmp = 0
for i in range(len(S)):
  if S[i] == 'W':
    ans+=i-tmp
    tmp+=1
print(ans)
### BUGGY CODE ###

n = int(input())

s = input()

x = []

for i in range(n):
    x.append(s[i])

m = len(set(x))

import itertools

cnt = 0
for i in range(1, m+1):
    p = list(itertools.combinations(s,i))
    cnt += sum(len(pp) == len(set(pp)) for pp in p)

print(cnt)


### FIXED CODE ###


n = int(input())

s = input()

x = []

for i in range(n):
    x.append(s[i])

import collections

clist = collections.Counter(x)

y = list(clist.values())

cnt = 1

for item in y:
    cnt = cnt * (item + 1)

cnt = cnt - 1
cnt = cnt % (10 ** 9 + 7)
print(cnt)
### BUGGY CODE ###

s = input()
q = int(input())

for _ in range(q):
    t = [x for x in input().split()]
    if t[0] == "1":
        s = s[::-1]
    else:
        if t[1] == "1":
            s = t[2] + s
        else:
            s += t[2]

print(s)

### FIXED CODE ###

from collections import deque
s = deque(input())
q = int(input())

rev = False

for _ in range(q):
    t = [x for x in input().split()]
    if t[0] == "1":
        rev = not rev
    else:
        if t[1] == "1":
            s.append(t[2]) if rev else s.appendleft(t[2])
        else:
            s.appendleft(t[2]) if rev else s.append(t[2])

if rev:
    s.reverse()
print("".join(s))
### BUGGY CODE ###

import numpy as np
n = int(input())
a = list(map(int, input().split()))
b = np.zeros(n)
for i in range(1,n):
    b[i-1] = a.count(i)
for i in b:
    print(int(i))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))

d = {}

for i in range(N - 1):
    if A[i] in d:
        d[A[i]].append(i + 2)
    else:
        d[A[i]] = [i + 2]

for i in range(1, N + 1):
    if i in d:
        print(len(d[i]))
    else:
        print(0)
### BUGGY CODE ###

from bisect import bisect_right as br
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(N)]

AB.sort()
A=[a for a,b in AB]
B=[b for a,b in AB]
works=[]
ans=0
for i in range(1,M+1):
  day=M-i
  latest=i
  #worksにlatest日以内に報酬を貰える仕事を追加する
  if not A or A[0]>latest:
    pass
  else:
    for _ in range(br(A,latest)):
      A=A[1:]
      works.insert(br(works,B[0]),B[0])
      B=B[1:]
  if not works:
    continue
  ans+=works.pop(-1)

print(ans)


### FIXED CODE ###

import heapq
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(N)]

AB.sort(reverse=True)
works=[]
heapq.heapify(works)
ans=0
for i in range(1,M+1):
  day=M-i
  latest=i
  while AB and AB[-1][0]<=latest:
    a,b=AB.pop()
    heapq.heappush(works,-b)
  if not works:
    continue
  ans-=heapq.heappop(works)

print(ans)
### BUGGY CODE ###

N = int(input())
S = input()

cand = ["RGB", "RBG", "GRB", "GBR", "BRG", "BGR"]

ans = S.count("R") * S.count("G") * S.count("B")
for i in range(N - 2):
    for d in range(1, N):
        if S[i:i + 2 * d + 1:d] in cand:
            ans -= 1

print(ans)

### FIXED CODE ###

N = int(input())
S = input()

cand = ["RGB", "RBG", "GRB", "GBR", "BRG", "BGR"]

ans = S.count("R") * S.count("G") * S.count("B")
for i in range(N - 2):
    for d in range(1, (N - i + 1) // 2):
        if S[i:i + 2 * d + 1:d] in cand:
            ans -= 1

print(ans)
### BUGGY CODE ###

H,n = map(int,input().split())
A = [0 for _ in range(n)]
B = [0 for _ in range(n)]
min_eff = 9999.
for i in range(n):
    A[i],B[i] = map(int,input().split())
    min_eff = min(min_eff,A[i]/B[i])

dp = [[int(H/min_eff+1) for _ in range(H+1)] for _ in range(n+1)]
for i in range(n+1):
    dp[i][0] = 0


for i in range(n):
    for h in range(H+1):
        idx = max(0,h-A[i])
        dp[i+1][h] = min(dp[i+1][idx] + B[i],dp[i][h])

print(int(dp[n][H]))


### FIXED CODE ###


H,n = map(int,input().split())
A = [0 for _ in range(n)]
B = [0 for _ in range(n)]
min_eff = 9999.
for i in range(n):
    A[i],B[i] = map(int,input().split())
    min_eff = min(min_eff,A[i]/B[i])

dp = [[int(H/min_eff+1) for _ in range(H+1)] for _ in range(n+1)]
for i in range(n+1):
    dp[i][0] = 0


for i in range(n):
    for h in range(H+1):
        idx = max(0,h-A[i])
        dp[i+1][h] = min(dp[i+1][idx] + B[i],dp[i][h])

print(int(dp[n][H]))
### BUGGY CODE ###

n = int(input())
lis = [1]
cou = 0
ans = 0
bo = []
for i in range(n):
    bo.append(int(input()))
for i in range(n):
    a = bo[cou]
    if a not in lis:
        lis.append(a)
    else:
        print("-1")
        break
    cou = a-1
    ans += 1
    if a == 2:
        print(ans)
        break

### FIXED CODE ###

n = int(input())
lis = []
p = 1
s = -1
for i in range(n):lis.append(int(input()))
for m in range(n):
    p = lis[p-1]
    if p == 2:
        s = m + 1
        break
print(s)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Tue Jan 21 16:49:00 2020

@author: matsui
"""

def cost(i,j):
    return abs(h[i]-h[j])

N,K=map(int,input().split())
h=[int(num) for num in input().split()]

dp=[0]*N
dp[1]=abs(h[0]-h[1])
   
for i in range(2,N):
    dp[i]=min([abs(h[i]-h[j])+dp[j] for j in range(max(0, i-K), i)])
    
print(dp[N-1])

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Tue Jan 21 16:49:00 2020

@author: matsui
"""



N,K=map(int,input().split())
h=[int(num) for num in input().split()]

dp=[0]*N
dp[1]=abs(h[0]-h[1])
   
def cost(h,N,K,dp):
    for i in range(2,N):
        dp[i]=min([abs(h[i]-h[j])+dp[j] for j in range(max(0, i-K), i)])
    return dp[-1]
    
print(cost(h,N,K,dp))
### BUGGY CODE ###

#!/usr/bin/env python3
#ABC138 E

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

s = input()
t = input()
n = len(s)
m = len(t)
f = [False]*26
f2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(n):
    f[alpha.index(s[i])] = True
for i in range(m):
    f2[alpha.index(t[i])] = True
for i in range(26):
    if not f[i] and f2[i]:
        print(-1)
        quit()
ans = 0
inde = s.index(t[0])
ans += inde+1
for i in range(1,m):
    s = s[inde+1:] + s[:inde+1]
    inde = s.index(t[i])
    ans += inde+1
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
#ABC138 E

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

s = input()
t = input()
n = len(s)
m = len(t)
f = [False]*26
f2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(n):
    f[alpha.index(s[i])] = True
for i in range(m):
    f2[alpha.index(t[i])] = True
for i in range(26):
    if not f[i] and f2[i]:
        print(-1)
        quit()
ans = 0
pre = s.index(t[0])
ans += pre+1
for i in range(1,m):
    s = s[pre+1:] + s[:pre+1]
    inde = s.index(t[i])
    ans += inde+1
    pre = inde
print(ans)
### BUGGY CODE ###

def sakuzyo(li):
    ct = 0
    found = 1
    while found:
        found = 0
        for i in range(len(li)-1):
            if (li[i] == "0" and li[i+1] == "1") or (li[i] == "1" and li[i+1] == "0"):
                del li[i:i+2]
                ct += 2
                found = 1
                break
    return ct
li = list(input())
print(sakuzyo(li))



### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

s = ns()
n = len(s)
b = s.count('0')
r = n - b
print(2 * min(b, r))
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding:utf-8 -*-
#from __future__ import print_function
import time
import sys
import io
import re
import math
start = time.clock()
i = 0
ans=[]
n=int(raw_input())
for _ in range(n):
    a=sys.stdin.readline().split()
    if a[0]=='insert': ans.insert(0,a[1])
    elif a[0]=='deleteFirst': ans.pop(0)
    elif a[0]=='deleteLast': ans.pop()
#    else: ans.remove(str(a[1]))
    else:
        if a[1] in ans:
            ans.remove(a[1])
#    print ans
print ' '.join(ans)

### FIXED CODE ###

import sys
import collections
n=int(raw_input())
ans=collections.deque()
while n:
    n-=1
    s=sys.stdin.readline().rstrip().split(' ')
    if s[0][0]=='i':
        ans.appendleft(s[1])
    elif s[0][-3]=='r':
        ans.popleft()
    elif s[0][-3]=='a':
        ans.pop()
    else:
        try:
            ans.remove(s[1])
        except:
            pass
sys.stdout.write(' '.join(ans))
print
### BUGGY CODE ###

import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

S = sys.stdin.buffer.readline().decode().rstrip()
N = len(S)

# ピッタリ払う
dp0 = [INF] * (N + 1)
# 1 多く払う
dp1 = [INF] * (N + 1)

dp0[0] = 0
dp1[0] = 1
for i, c in enumerate(S):
    dp0[i + 1] = min(dp0[i] + int(c), dp1[i] + 10 - int(c))
    dp1[i + 1] = min(dp0[i] + int(c) + 1, dp1[i] + 10 - int(c) - 1)
# print(dp0)
# print(dp1)
print(dp0[-1])


### FIXED CODE ###

import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N = sys.stdin.buffer.readline().decode().rstrip()

S = []
T = []
for c in N:
    S.append(int(c))
    T.append(9 - int(c))
T[-1] += 1
i = len(T) - 1
while T[i] == 10:
    T[i] = 0
    T[i - 1] += 1
    i -= 1

N = len(S)

# maekaramiteku
# dp[i][j]: i まで見て最小の答え、反転してるかどうか
dp = [[IINF, IINF] for _ in range(N + 1)]
dp[0][0] = 0
dp[0][0] = 0
for i in range(N):
    # 1 使って反転できる
    dp[i + 1][0] = min(dp[i][0] + S[i], dp[i][1] + 1 + S[i])
    dp[i + 1][1] = min(dp[i][1] + T[i], dp[i][0] + 1 + T[i])

print(min(dp[-1]))