Harryxun/stf_run huggingface dataset:
import sys
input = sys.stdin.readline

def dfs(v, p, c):
    color[v] = c
    for e in graph[v]:
        if e[0] == p: continue
        if e[1] % 2: dfs(e[0], v, 1-c)
        else: dfs(e[0], v, c)


n = int(input())
color = [-1 for _ in range(n)]
graph = [[] for _ in range(n)]

for i in range(n-1):
    u, v, w = [int(x) for x in input().split()]
    u, v = u - 1, v - 1
    graph[u].append((v, w))
    graph[v].append((u, w))

dfs(0, -1, 1)
for i in range(n):
    print(color[i])

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

def dfs(v, p, c):
    color[v] = c
    for e in graph[v]:
        if e[0] == p: continue
        if e[1] % 2: dfs(e[0], v, 1-c)
        else: dfs(e[0], v, c)


n = int(input())
color = [-1 for _ in range(n)]
graph = [[] for _ in range(n)]

for i in range(n-1):
    u, v, w = [int(x) for x in input().split()]
    u, v = u - 1, v - 1
    graph[u].append((v, w))
    graph[v].append((u, w))

dfs(0, -1, 1)
for i in range(n):
    print(color[i])
#!/usr/bin/env python
# coding:utf-8
import os, sys
import math

N = input()
K = input()
X=input()
Y=input()
if N-K >= 0:
    print X*K + Y*(N-K)
else:
    pritn X*K





### FIXED CODE ###

#!/usr/bin/env python
# coding:utf-8
import os, sys
import math

N = input()
K = input()
X=input()
Y=input()
if N <= K:
    print X*N
else:
    print X*K + Y*(N-K)
def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    A = [int(i) for i in input().split()]
    from collections import Counter
    from math import gcd
    c = Counter(A)
    bl = set()
    for k, v in c.items():
        if v >= 2:
            L *= k
            bl.add(k)
    if c[1] == 1:
        return print(1)
    elif c[1] > 1:
        return print(0)
    A.sort()

    ans = 0
    L = 1
    for a in A:
        if a in bl:
            continue
        v = gcd(L, a)
        if v not in A:
            ans += 1
        L *= a
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    A = [int(i) for i in input().split()]
    A.sort()
    B = [True]*(10**6+1)

    from collections import Counter
    c = Counter(A)
    bl = set()
    for k, v in c.items():
        if v >= 2:
            bl.add(k)

    ans = 0
    for a in set(A):
        if a not in bl and B[a]:
            ans += 1
        for i in range(1, 10**6):
            if 10**6 < a*i:
                break
            B[a*i] = False
    print(ans)


if __name__ == '__main__':
    main()
while True:
 input('')

### FIXED CODE ###

t=[]
while True:
    x = str(input(""))
    if x == "0":
        break
    else:
        t.append(x)
for i,v in enumerate(t):
    print("Case",str(i+1)+":",t[i])
K = int(input())
S = input()

x = len(s)

if x > K:
  print(S[1:] + '...')
else:
  print(S)

### FIXED CODE ###

K = int(input())
S = input()
x = len(S)
 
if x <= K:
    print(S)
else:
    print(S[:K] + '...')
import numpy as np

N = int(input())
a = []
for i in range(N):
    a.append(int(input()))

mean = np.mean(a)

idx = np.abs(np.asarray(a) - mean).argmin()

print(idx)



### FIXED CODE ###

import numpy as np

N = int(input())
a = [int(i) for i in input().split()]

mean = np.mean(a)

idx = np.abs(np.asarray(a) - mean).argmin()

print(idx)
import copy

n = int(input())
max_1 = None
max_2 = None

for i in range(n):
    a = int(input())
    if max_1 is None:
        max_i = [i]
        max_1 = a
    elif max_1 == a:
        max_i.append(i)
    elif max_1 < a:
        max_2 = max_1
        max_i = [i]
        max_1 = a
    elif max_2 < a:
        max_2 = a
    
if len(max_i) >= 2:
    out_list = [max_1 for i in range(n)]
else:
    out_list = [max_1 for i in range(n)]
    out_list[max_i[0]] = max_2
    
print("\n".join(map(str, out_list)))

### FIXED CODE ###


n = int(input())
a = []

for i in range(n):
    a.append(int(input()))
    
a_copy = list(a)
a.sort(reverse=True)

max_1 = a[0]
max_count = a.count(max_1)

for i in a:
    if i < max_1:
        max_2 = i
        break
        
for a in a_copy:
    if a == max_1 and max_count == 1:
        print(max_2)
    else:
        print(max_1)
N = int(input())
A = list(map(int,input().split()))
import fractions
X = A[0]
for i in range(1, N):
    X = X // fractions.gcd(X, A[i]) * A[i] 

output = 0
for i in range(N):
    output += int(X/A[i])%(10**9+7)
    if output > 10**9+7:
        output = output % (10**9+7)
print(output)

### FIXED CODE ###

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

import fractions

X = A[0]
for i in range(1, N):
    X = X*A[i] // fractions.gcd(X, A[i])

output = 0
D =10**9+7
X = X%D

for i in range(N):
    output += X*pow(A[i],D-2,D)%D
    output = output % (10**9+7)
print(int(output))
n,a,b=map(int,input().split())
if n*a>b:
  print(b)
else n*a<=b:
  print(n*a)

### FIXED CODE ###

n,a,b=map(int,input().split())
ans=min(n*a,b)
print(ans)
N = input()

s = "abcdefghijklmnopqrstuvwxyz"
ans = ""
n, m = 0, 0

for i in range(1, 1000):
    m += 26 ** i
    if N <= m:
        n = i
        break

for i in range(n):
    a, b = divmod(N, 26)
    N = a
    if b == 0:
        ans += s[25]
        N -= 1
    else:
        ans += s[b-1]

ans1 = ''.join(list(reversed(ans)))
print(ans1)

### FIXED CODE ###

if input().isupper():
  print("A")
else:
  print("a")
from collections import Counter
N,K = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
d = [a for a in Counter(A).values()]
tmp = 0
for i in range(min(K,len(d)+1)):
    tmp += max(d)
    d.remove(max(d))
print(len(A)-tmp)


### FIXED CODE ###

from collections import Counter
N,K = (int(i) for i in input().split())
d = Counter([int(i) for i in input().split()])
if len(d) <= K:
    print(0)
    exit()

tmp = 0
for _,p in d.most_common(K):
    tmp += p
print(N-tmp)
import bisect

N=int(input())
A=[int(i) for i in input().split(" ")]
A=sorted(A)
traceback=[]

if A[0]>=0:
    minus=[A[0]]
    plus=A[1::]
elif A[-1]<=0:
    minus=A[:-1:]
    plus=A[-1]
else:
    index=bisect.bisect_left(A,0)
    minus=A[:index:]
    plus=A[index::]

print(sum(plus)-sum(minus))
m=minus.pop(0)
for p in plus[:-1:]:
    print(m,p)
    m=m-p
print(plus[-1],m)
p=plus[-1]-m
for m in minus:
    print(p,m)
    p=p-m


### FIXED CODE ###

import bisect

N=int(input())
A=[int(i) for i in input().split(" ")]
A=sorted(A)
traceback=[]

if A[0]>=0:
    minus=[A[0]]
    plus=A[1::]
elif A[-1]<=0:
    minus=A[:-1:]
    plus=[A[-1]]
else:
    index=bisect.bisect_left(A,0)
    minus=A[:index:]
    plus=A[index::]

print(sum(plus)-sum(minus))
m=minus.pop(0)
for p in plus[:-1:]:
    print(m,p)
    m=m-p
print(plus[-1],m)
p=plus[-1]-m
for m in minus:
    print(p,m)
    p=p-m
args=input().split()

n=int(args[0])
s=args[1]

if n % 2 == 1:
  print('No')
else:
  half=n/2
  s1=s[half:]
  s2=s[:half]
  print('No' if s1!=s2 else 'Yes')
  

### FIXED CODE ###

n = int(input())
s = input()
if n % 2:
    print("No")
    exit()
half = s[0:n // 2]
print("Yes" if s == half + half else "No")
f=lambda:map(int,input().split())
n,st,sa=f()
st-=1
sa-=1
g=[[] for _ in range(n)]
for _ in range(n-1):
  a,b=f()
  g[a-1].append(b-1)
  g[b-1].append(a-1)
def dfs(v,p=-1,d=0):
  l[v]=d
  for c in g[v]:
    if c==p: continue
    dfs(c,v,d+1)
def dist(s):
  global l
  l=[0]*n
  dfs(s)
  return l
lt=dist(st)
la=dist(sa)
m=0
for i in range(n):
  if lt[i]<la[i]: m=max(m,la[i])
print(m-1)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
f=lambda:map(int,input().split())
n,st,sa=f()
st-=1
sa-=1
g=[[] for _ in range(n)]
for _ in range(n-1):
  a,b=f()
  g[a-1].append(b-1)
  g[b-1].append(a-1)
def dfs(v,p=-1,d=0):
  l[v]=d
  for c in g[v]:
    if c==p: continue
    dfs(c,v,d+1)
def dist(s):
  global l
  l=[0]*n
  dfs(s)
  return l
lt=dist(st)
la=dist(sa)
m=0
for i in range(n):
  if lt[i]<la[i]: m=max(m,la[i])
print(m-1)
import itertools

N, M = map(int,input().split())

p = [i for i in range(N)] #0スタート
root = []

for i in range(M):
  a,b = map(int,input().split())
  root.append([a-1,b-1])

#print(root)
pattern = list(itertools.permutations(p))

ans = 0
for i in range(len(pattern)):
  Flag = [0]*N
  Flag[0] = 1
  now = 0
  last = False
  for j in range(N-1):
    if now == root[pattern[i][j]][0]:
      now = root[pattern[i][j]][1]
    elif now == root[pattern[i][j]][1]:
      now = root[pattern[i][j]][0]
    else:
      break
    if Flag[now] != 0:
      break
    else:
      Flag[now] = 1
      if j == N-2:
        last = True
  if last:
    ans += 1
print(ans)

### FIXED CODE ###

import itertools
import sys

N, M = map(int,input().split())

if M < N-1:
  print(0)
  sys.exit()

p = [i for i in range(N)] #点の数
root = []
for i in range(M):
  a,b = map(int,input().split())
  root.append((a-1,b-1))

#たどる点の順番の全探索
pattern = list(itertools.permutations(p))
#print(pattern)

ans = 0
for i in range(len(pattern)):
  if pattern[i][0] != 0:
    break
  Flag = True
  for j in range(N-1):
    if (pattern[i][j], pattern[i][j+1]) in root:
      continue
    elif (pattern[i][j+1], pattern[i][j]) in root:
      continue
    else:
      Flag = False
      break
  if Flag:
    ans += 1
print(ans)
N = int(input())
S = str(input())

white = 0
black = 0
first_black_index = 0
end_index = N

while S[first_black_index] == ".":
  first_black_index += 1
  if first_black_index == N:
    print(0)
    break

last_black_index = len(S)
if first_black_index != N:
  while S[len(S)] == "#":
    last_black_index -= 1
    if last_black_index == 0:
      print(0)
      break


if first_black_index != N and last_black_index != 0:
  S = S[first_black_index:last_black_index+1]

  for i in range(len(S)):
    if S[i] == "#":
      black +=1
    else:
      white +=1

  print(min(white,black))


### FIXED CODE ###

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

white = S.count(".")
black = 0
ans = S.count(".")

for i in range(N):
  if S[i] == ".":
    white -=1
  else:
    black +=1
  ans = min(ans,white+black)

print(ans)
#dfs
import sys
sys.setrecursionlimit(10 ** 7)

#dfs
M = int(input())
L = []
for i in range(M):
    d, c = map(int, input().split())
    L.extend([d] * c)

answer = 30

def dfs(count, l):
    global answer
    if len(l) == 1:
        #print(count)
        answer = min(answer, count)
    else:
        for i in range(len(l)-1):
            sum = l[i] + l[i+1]
            result = l[:i] + [int(x) for x in list(str(sum))] + l[i+2:]
            #print(result)
            dfs(count+1, result)

dfs(0, L)
print(answer)


### FIXED CODE ###

import sys
import numpy as np

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

M = ni()
D = [] ; C = []

for i in range(M):
    d, c = na()
    D.append(d)
    C.append(c)

D = np.array(D) ; C = np.array(C)
#桁数の9倍とそれぞれの数字の総和をx
x = C.sum() * 9 + (C * D).sum()
# 18以下で終了
answer = (x + 8) // 9 - 2
print(answer)
N = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]

s = 0
pre_food = A[0]
for food in A:
    s += B[food]
    if food - pre_food == 1 : s += C[food]
    pre_food = food

print(s)

### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]

s = 0
pre_food = A[0]
for food in A:
    s += B[food-1]
    if food - pre_food == 1 : s += C[food-2]
    pre_food = food

print(s)
a, b, c = list(map(intl, input().split()))
if a * b >= c:
  print(c)
else:
  print(a * b)

### FIXED CODE ###

a, b, c = list(map(int, input().split()))
if a * b >= c:
  print(c)
else:
  print(a * b)
def gcd(a, b):
    if a % b == 0:
        return b
    else:
        return gcd(b, a%b)

A, B = map(int, input().split())
g = gcd(A, B)

cnt = 1  # 1は必ず含まれるので

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

data = primes(g)

for d in data:
    if g % d == 0:
        cnt += 1

print(cnt)

### FIXED CODE ###

# 1と素因数の個数の和が答え
# つまりAの素因数を求めて、その中でBの約数となっているものを数えればよい。

def p_factors(x): # prime_factors
    ret = [1]
    check = 2
    while (True):
        if x % check == 0:
            ret.append(check)
            while x % check == 0:
                x = x // check
        check += 1
        if x == 1 or check > int(x**0.5)+1:
            break
    if x != 1:
        ret.append(x)
    return ret

def main():
    A, B = map(int, input().split())
    factors = p_factors(A)
    cnt = 0
    for f in factors:
        if B % f == 0:
            cnt += 1
    print(cnt)

if __name__ == "__main__":
    main()
n= int(input())
G=[[] for i in range(n+1)]

for i in range(n-1):
	a,b,c=map(int, input().split())
	G[a].append([b,c])
	G[b].append([a,c])

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


D=[None]*(n+1)
 
def dfs(x,d):
    D[x]=d
    for yy,dd in G[x] :
        if D[yy] is not None:
            continue
        dfs(yy,dd+d)
dfs(k,0)

for i in range(q):
    x, y = map(int, input().split())
    print(D[x] + D[y])

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n= int(input())
G=[[] for i in range(n+1)]

for i in range(n-1):
	a,b,c=map(int, input().split())
	G[a].append([b,c])
	G[b].append([a,c])

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


D=[None]*(n+1)
 
def dfs(x,d):
    D[x]=d
    for yy,dd in G[x] :
        if D[yy] is not None:
            continue
        dfs(yy,dd+d)
dfs(k,0)

for i in range(q):
    x, y = map(int, input().split())
    print(D[x] + D[y])
s = sort(input())
if s[0] == 'a' and s[1] == 'b' and s[2] == 'c':
	print('Yes')
else:
	print('No')

### FIXED CODE ###

s = sorted(input())
if s[0] == 'a' and s[1] == 'b' and s[2] == 'c':
	print('Yes')
else:
	print('No')
yen=int(input())
big=yen//500
small=(yen-500*big)//5
print(1000*big+5*small

### FIXED CODE ###

yen=int(input())
big=yen//500
small=(yen-500*big)//5
print(1000*big+5*small)
#https://atcoder.jp/contests/abcXXX
import __input
#-------------------------以下を提出-------------------------

p,q,r = map(int,input().split())
ans = 999
ans = min(p+q,ans)
ans = min(p+r,ans)
ans = min(q+r,ans)

print(ans)

### FIXED CODE ###


p,q,r = map(int,input().split())
ans = 999
ans = min(p+q,ans)
ans = min(p+r,ans)
ans = min(q+r,ans)

print(ans)
x = Range(1, 100)

print(x*x)


### FIXED CODE ###


x = int(input())

print(x**3)
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.append(100)
B.append(100)
ans=0
for i in range(1,N+1):
	ans+=B[A[i-1]-1]
	if A[i-1]==A[i]-1:
		ans+=C[A[i-2]]
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.append(100)
B.append(100)
C.insert(0,0)
ans=0
for i in range(1,N+1):
	ans+=B[A[i-1]-1]
	if A[i-1]==A[i]-1:
		ans+=C[A[i-1]]
print(ans)
X, Y = map(int, input().split())
s = X + Y/2
print(s)



### FIXED CODE ###

x,y = map(int,input().split())

s = x + y//2

print(s)
N = input()
V = input().split()
C = input().split()
ret_X_Y = 0

for i in range(len(V)):
    if (V[i] - C[i]) > 0:
        ret_X_Y += V[i] - C[i]
print(ret_X_Y)

### FIXED CODE ###

N = input()
V = input().split()
C = input().split()
ret_X_Y = 0
V = [int(i) for i in V]
C = [int(i) for i in C]
for i in range(len(V)):
    if (V[i] - C[i]) > 0:
        ret_X_Y += V[i] - C[i]
print(ret_X_Y)
S = int(input()).split()
print(max(S))


### FIXED CODE ###


S = input().split()
X = int(S[0])+int(S[1])
Y = int(S[0])-int(S[1])
Z = int(S[0])*int(S[1])
if X >= Y:
    if X >= Z:
        print(X)
    else:
        print(Z)
else:
    if Y >= Z:
        print(Y)
    else:
        print(Z)
x=input()
tmp=100
for i in range(10000):
  if tmp>=x:
    print(i)
    break
  tmp+=tmp//100

### FIXED CODE ###

x=int(input())
tmp=100
for i in range(10000):
  if tmp>=x:
    print(i)
    break
  tmp+=tmp//100
a = input()

if a[0] == a[1] and a[2] == a[3]: //AABB
	print("Yes")
elif a[0] == a[2] and a[1] == a[3]: //ABAB
	print("Yes")
elif a[0] == a[3] and a[1] == a[2]: //ABBA
	print("Yes")
else:
  	print("No")

### FIXED CODE ###

a = input()

if a[0] == a[1] == a[2] == a[3]:
    print("No")
elif a[0] == a[1] and a[2] == a[3]:
    print("Yes")
elif a[0] == a[2] and a[1] == a[3]:
    print("Yes")
elif a[0] == a[3] and a[1] == a[2]:
    print("Yes")
else:
    print("No")
import math
def agc033_a():
  h, w = map(int, input().split())
  grid = [[s for s in str(input())] for _ in range(h)]

  # 黒マスからの距離(#は0)
  dist = [[math.inf] * w for _ in range(h)]
  for i in range(h):
    for j in range(w):
      if grid[i][j] == '#':
        dist[i][j] = 0

  def ask_dist(i, j):
    adj = math.inf
    if 0 < i: adj = min(adj, dist[i-1][j])
    if i < h-1: adj = min(adj, dist[i+1][j])
    if 0 < j: adj = min(adj, dist[i][j-1])
    if j < w-1: adj = min(adj, dist[i][j+1])
    if adj != math.inf:
      return adj + 1
    else:
      return math.inf

  # 1往復したら距離確定する？？ TLEするかも？？
  d_max = 0
  for i in range(h):
    for j in range(w):
      if dist[i][j] != math.inf: continue
      d_tmp = ask_dist(i, j)
      if d_tmp != math.inf:
        dist[i][j] = d_tmp
        d_max = max(d_max, d_tmp)
  for i in range(h-1, -1, -1):
    for j in range(w-1, -1, -1):
      if dist[i][j] != math.inf: continue
      d_tmp = ask_dist(i, j)
      if d_tmp != math.inf:
        dist[i][j] = d_tmp
        d_max = max(d_max, d_tmp)
  print(d_max)

agc033_a()

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque

def agc033_a():
    H, W = map(int, readline().split())
    dist = [[-1] * W for _ in range(H)]
    que = deque()
    for i, ln in enumerate(read().split()):
        for j, c in enumerate(ln.strip().decode('UTF-8')):
            if c == '#':
                que.append((i, j))
                dist[i][j] = 0

    while que:
        x, y = que.popleft()
        for i, j in ((x-1, y), (x, y-1), (x, y+1), (x+1, y)):
            if i < 0 or H-1 < i or j < 0 or W-1 < j: continue
            if dist[i][j] != -1: continue
            dist[i][j] = dist[x][y] + 1
            que.append((i, j))

    ans = 0
    for row in dist:
        ans = max(max(row), ans)
    print(ans)

agc033_a()
a,b,c,d = input()
print('Yes' if (a == b and b == c ) or (b == c and C == d ) else 'No')

### FIXED CODE ###

a,b,c,d = input()
print('Yes' if (a == b and b == c ) or (b == c and c == d ) else 'No')
n,m,k = list(map(int,input().split()))
a = list(map(int,input().split()))
b = list(map(int,input().split()))

import numpy as np
import bisect
a = np.cumsum(a)
b = np.cumsum(b)
ans = 0
r = m
for i in range(n+1):
  if a[i] > k:
    break
  while a[i] + b[r] > k:
    r -= 1
  ans = max(ans, i+r)

print(ans)

### FIXED CODE ###

n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
sa = [0] * (n + 1)
sb = [0] * (m + 1)
for i in range(n):
  sa[i + 1] = sa[i] + a[i]
for i in range(m):
  sb[i + 1] = sb[i] + b[i]
r = m
ans = 0
for i in range(n + 1):
  if sa[i] > k:
    break
  while sa[i] + sb[r] > k:
    r -= 1
  ans = max(ans, i + r)
print(ans)
N, u, v = map(lambda x: int(x)-1, input().split())
N += 1
edges = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]
adj = [[] for _ in range(N)]
for a, b in edges:
    adj[a].append(b)
    adj[b].append(a)

# bfs from v
dist_from_v = [-1]*N
dist_from_v[v] = 0
Q = {v}
while Q:
    tmp = set()
    for cur in Q:
        for next in adj[cur]:
            if dist_from_v[next] == -1:
                dist_from_v[next] = dist_from_v[cur]+1
                tmp.add(next)
    Q = tmp

# bfs from u
dist_from_u = [-1]*N
dist_from_u[u] = 0
Q = {u}
while Q:
    tmp = set()
    for cur in Q:
        for next in adj[cur]:
            if dist_from_u[next] == -1:
                if dist_from_u[cur]+1 < dist_from_v[next]:
                    dist_from_u[next] = dist_from_u[cur]+1
                    tmp.append(next)
    Q = tmp


dst_u = dist_from_u.index(max(dist_from_u))
dist_v_dst = dist_from_v[dst_u]
ans = dist_v_dst-1
print(ans)


### FIXED CODE ###

N, u, v = map(lambda x: int(x)-1, input().split())
N += 1
edges = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]
adj = [[] for _ in range(N)]
for a, b in edges:
    adj[a].append(b)
    adj[b].append(a)

# bfs from v
dist_from_v = [-1]*N
dist_from_v[v] = 0
Q = {v}
while Q:
    tmp = set()
    for cur in Q:
        for next in adj[cur]:
            if dist_from_v[next] == -1:
                dist_from_v[next] = dist_from_v[cur]+1
                tmp.add(next)
    Q = tmp

# bfs from u
dist_from_u = [-1]*N
dist_from_u[u] = 0
Q = {u}
while Q:
    tmp = set()
    for cur in Q:
        for next in adj[cur]:
            if dist_from_u[next] == -1:
                if dist_from_u[cur]+1 < dist_from_v[next] or True:
                    dist_from_u[next] = dist_from_u[cur]+1
                    tmp.add(next)
    Q = tmp

ans = 0
for i in range(N):
    if dist_from_u[i] < dist_from_v[i]:
        ans = max(ans, dist_from_v[i]-1)
print(ans)
exit()

dst_u = dist_from_u.index(max(dist_from_u))
dist_v_dst = dist_from_v[dst_u]
ans = dist_v_dst-1
print(ans)
import sys


def g(a, b):
    d = abs(a - b)
    return g(d, a) if a % d != 0 else d


for line in sys.stdin:
    a, b = map(int, line.split())
    c = g(a, b)
    print(c, a * b // gcd)

### FIXED CODE ###

import sys
 
def gcd(inta, intb):
    large = max(inta, intb)
    small = min(inta,intb)
    mod = large % small
    if mod ==0:
        return small
    else:
        return gcd(small, mod) 
     
def lcm(inta, intb, intgcd):
    return (inta * intb // intgcd)
 
sets = sys.stdin.readlines()
for line in sets:
    a, b = map(int, line.split())
    c = gcd(a, b)
    print(c, lcm(a, b, c))
N,Q=map(int,input().split())
S=input()
ls=[];rs=[]
for i in range(Q):
    l,r=map(int,input().split())
    n=0;a=False
    for k in S[(l-1):(r)]:
        if k!="A" and a==False:
            pass
        elif k=="A":
            a=True
        elif a:
            if k=="C":
                n+=1
            else:
                a=False
    print(n)
    
    

### FIXED CODE ###

b=input()
if b=="A":
    print("T")
elif b=="C":
    print("G")
elif b=="G":
    print("C")
elif b=="T":
    print("A")
a,b=input().split()
print(sum(i==i[::-1] for i in range(int(a), int(b)+1)))

### FIXED CODE ###

a,b=map(int,input().split())
print(sum(i==i[::-1] for i in map(str,range(a,b+1))))
mod=10**9+7
n,k=map(int,raw_input().split())
a=map(int,raw_input().split())
dp=[[[0]*(1<<8) for _ in xrange(n+1)] for _ in xrange(n+1)]
for i in xrange(n):
    dp[i+1][1][a[i]]=1
for i in xrange(n):
    for j in xrange(n):
        for l in xrange(1<<8):
            dp[i+1][j+1][a[i]^l]+=(j+1)*dp[i][j][l]%mod
            dp[i+1][j][l]+=dp[i][j][l]%mod
ans=0
for j in xrange(1,n+1):
    ans=(ans+dp[n][j][k])%mod
print(ans)

### FIXED CODE ###

mod=11
n,k=map(int,raw_input().split())
k=(k-8)%mod
last=7*n-7*2-2
idx=-1
for i in xrange(1,last+1):
    if 3*(i+i+1+i+2)%mod==k:
        idx=i
        break
r2idx=r1idx=-1
for i in xrange(1,n+1):
    if (7*i-1-idx)%11==0:
        r2idx=7*i-1
        break
for i in xrange(1,n+1):
    if (7*i-idx)%11==0:
        r1idx=7*i
        break
if idx==-1:
    print(0)
    exit()
if r1idx==-1:
    if r2idx==-1:
        print((last-idx)/11+1)
    else:
        print((last-idx)/11+1-(last-r2idx)/(7*11)-1)
else:
    if r2idx==-1:
        print((last-idx)/11+1-(last-r1idx)/(7*11)-1)
    else:
        print((last-idx)/11+1-(last-r2idx)/(7*11)-1-(last-r1idx)/(7*11)-1)

#print r1idx,r2idx,idx
#print((last-idx)/11+1-(last-r2idx)/(n*11)-1-(last-r1idx)/(n*11)-1)