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

h,w = (int(x) for x in input().split())
ab = []
for _ in range(h):
    a = input()
    a = a+'#'
    ab.append(list(a))
ab.append(list('#'*w))
dp = [[100000000000000000 for a in range(w+1)] for b in range(h+1)]
if ab[0][0] == '#':
    dp[0][0] = 1
else:
    dp[0][0] = 0
step = [[0, 0]]
 
while len(step) > 0:
    y, x = step.pop(0)
    
    if h-1<y or w-1 < x:continue
    
    if ab[y+1][x] == '#':
        step.append([y+1, x])
        dp[y+1][x] = min(dp[y][x] + 1, dp[y+1][x])
    else:
        step.append([y+1, x])
        dp[y+1][x] = min(dp[y][x], dp[y+1][x])
    if ab[y][x+1] == '#':
        step.append([y, x+1])
        dp[y][x+1] = min(dp[y][x] + 1, dp[y][x+1])
    else:
        step.append([y, x+1])
        dp[y][x+1] = min(dp[y][x],dp[y][x+1])
 
print(dp[h-1][w-1])

### FIXED CODE ###

h,w = (int(x) for x in input().split())
ab = []
for _ in range(h):
    a = input()
    a = a+'#'
    ab.append(list(a))
ab.append(list('#'*w))
dp = [[100000000000000000 for a in range(w+1)] for b in range(h+1)]
if ab[0][0] == '#':
    dp[0][0] = 1
else:
    dp[0][0] = 0
step = [[0, 0]]
 
while len(step) > 0:
    y, x = step.pop(0)
    
    if h-1<y or w-1<x :continue
    
    if dp[y+1][x] == 100000000000000000:
        step.append([y+1, x])
    if dp[y][x+1] == 100000000000000000:
        step.append([y, x+1])

    if ab[y][x+1] == '#' and ab[y][x] == '.' :
        dp[y][x+1] = min(dp[y][x] + 1, dp[y][x+1])
    else:
        dp[y][x+1] = min(dp[y][x],dp[y][x+1])
    
    if ab[y+1][x] == '#' and ab[y][x] == '.' :
        dp[y+1][x] = min(dp[y][x] + 1, dp[y+1][x])
    else:
        dp[y+1][x] = min(dp[y][x], dp[y+1][x])
    
 
print(dp[h-1][w-1])
### BUGGY CODE ###

from collections import Counter
N = int(input().strip())
counter = Counter()
for i in list(map(int, input().strip().split(' '))):
  counter += Counter([i-1,i,i+1])

print(counter.most_common(1)[0][1])

### FIXED CODE ###

from collections import Counter
N = int(input().strip())
counter = Counter()
for i in list(map(int, input().strip().split(' '))):
  counter[i-1] += 1
  counter[i] += 1
  counter[i+1] += 1

print(counter.most_common(1)[0][1])
### BUGGY CODE ###

N,K = map(int,input().split())
H = [int(input()) for _ in range(N)]
ans = 0
H.sort()
for i in range(N-K+1):
    a = H[i:i+K]
    b = max(a)-min(a)
    if i == 0:
        ans = b
    elif ans > b:
        ans = b
print(ans)

### FIXED CODE ###

N,K = map(int,input().split())
H = [int(input()) for _ in range(N)]
ans = 10**10
H.sort()
for i in range(N-K+1):
    ans = min(ans,H[i+K-1]-H[i])
print(ans)
### BUGGY CODE ###

def tuika(a,b):
    if a in dicSet:
        dic[a].add(b)
    else:
        dic[a] = set()
        dic[a].add(b)
        dicSet.add(a)



n,m = list(map(int,input().split()))

dic = dict()
dicSet = set()

for i in range(m):
    a,b = list(map(int,input().split()))
    if a in dicSet:
        dic[a].add(b)
    else:
        dic[a] = set()
        dic[a].add(b)
        dicSet.add(a)

    if b in dicSet:
        dic[b].add(a)
    else:
        dic[b] = set()
        dic[b].add(a)
        dicSet.add(b)

for i in dicSet:
    for j in dic[i]:
        dic[j] = dic[j] | dic[i]

ans = 1

for i in dicSet:
    long = len(dic[i])
    if long > ans:
        ans = long

#print(dic)

print(ans)

### FIXED CODE ###

import collections

def searchRoot(n):
    par = parList[n]
    if n == par:
        if len(q) > 0:
            rootIn(q,n)
        return n
    else:
        q.append(n)
        return(searchRoot(par))

def rootIn(q,root):
    while len(q) > 0:
        parList[q.popleft()] = root

n,m = list(map(int,input().split()))
q = collections.deque()

parList = [i for i in range(n+1)]

for i in range(m):
    a,b = list(map(int,input().split()))
    aRoot = searchRoot(a)
    bRoot = searchRoot(b)
    if aRoot != bRoot:
        parList[max(aRoot,bRoot)] = min(aRoot,bRoot)
    
#print(parList)

ansDic = dict()
rootSet = set()
for i in range(1,n+1):
    root = searchRoot(i)
    if root in rootSet:
        ansDic[root] += 1
    else:
        rootSet.add(root)
        ansDic[root] = 1

ans = 1
for i in rootSet:
    if ansDic[i] > ans:
        ans = ansDic[i]

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

import fractions
from functools import reduce

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

N = int(input())
l = list(map(int, input().split(" ")))

p = lcm_list(l)
c = 0
z = 10 ** 9 + 7
for i in l:
  c += p // i % z
print(c % z)

### FIXED CODE ###

import fractions
from functools import reduce
 
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

N = int(input())
l = list(map(int, input().split(" ")))
 
p = lcm_list(l)
c = 0
for i in l:
  c += p // i
print(c % (10 ** 9 + 7))
### BUGGY CODE ###

N = int(input())
res = 0
for i in range(1, N +1):
    if i < N:
        res += i % (i + 1)

print(res)

### FIXED CODE ###

N = int(input())

print((N-1)*N //2 )
### BUGGY CODE ###

N = int(input())
A = []
for n in range(N):
    A.append(int(input()))
for i in range(N):
    new = A[:]
    new.pop(i)
    print(max(new))

### FIXED CODE ###

N = int(input())
A = []
for n in range(N):
    A.append(int(input()))

A_sort = sorted(A)
first = A_sort[-1]
second = A_sort[-2]
if first == second:
    for n in range(N):
        print(first)
else:
    for i in range(N):
        if A[i] == first:
            print(second)
        else:
            print(first)
### BUGGY CODE ###

N, M, K = map(int, input().split())
A = [0] + list(map(int, input().split()))
B = [0] + list(map(int, input().split()))

for i in range(1, N+1):
    A[i] += A[i-1]
for i in range(1, M+1):
    B[i] += B[i-1]

ans = 0

for a_index in range(N+1):
    left = K - A[a_index]
    if left < 0: break
    score = a_index

    for b_index in reversed(range(M+1)):
        if B[b_index] <= left:
            score += b_index
            break

    ans = max(ans, score)

print(ans)

### FIXED CODE ###

N, M, K = map(int, input().split())
A = [0] + list(map(int, input().split()))
B = [0] + list(map(int, input().split()))

for i in range(1, N+1):
    A[i] += A[i-1]
for i in range(1, M+1):
    B[i] += B[i-1]

ans = 0

b_index = M

for a_index in range(N+1):
    left = K - A[a_index]
    if left < 0: continue

    while left - B[b_index] < 0:
        b_index -= 1

    ans = max(ans, a_index + b_index)

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

# ans = 全通り - nCa - nCb
#     = 2^n - 1 - nCa - nCb

def pow(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def comb_num_mod(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

n, a, b = map(int, input().split())

mod = (10**9) + 7

num_all = pow(2, n) - 1

nca = comb_num_mod(n, a, mod=mod)
ncb = comb_num_mod(n, b, mod=mod)

print(num_all - nca - ncb)

### FIXED CODE ###

# ans = 全通り - nCa - nCb
#     = 2^n - 1 - nCa - nCb
def comb(n,r,mod=10**9+7):
    a=1
    b=1
    r = min(r,n-r)
    for i in range(r):
        a = a*(n-i)%mod
        b = b*(i+1)%mod
    return a*pow(b,mod-2,mod)%mod

n, a, b = map(int, input().split())

mod = (10**9) + 7

num_all = pow(2, n, mod) - 1
nca = comb(n, a, mod=mod)
ncb = comb(n, b, mod=mod)

ans = num_all - nca - ncb
ans %= mod

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

import sys
H, W, N = map(int,input().split())
if N ==0:
  print((H-2)*(W-2))
  for i in range(9): print(0)
  sys.exit()
  
ans =[(H-2)*(W-2)]+[0]*9
blacks = [[0 for i in range(W+2)] for j in range(H+2)]
for i in range(N):
  a, b = map(int,input().split())
  for dx in [-1,0,1]:
    for dy in [-1,0,1]:
      if 2 <= a+dx <H and 2 <= b+dy <W:
        ans[blacks[a+dx][b+dy]]-=1
        ans[blacks[a+dx][b+dy]+1]+=1
      blacks[a+dx][b+dy]+=1
        
for i in range(10): print(ans[i])

### FIXED CODE ###

import sys
from collections import defaultdict

H, W, N = map(int,input().split())
if N ==0:
  print((H-2)*(W-2))
  for i in range(9): print(0)
  sys.exit()
  
ans =[(H-2)*(W-2)]+[0]*9
blacks = defaultdict(int)
for i in range(N):
  a, b = map(int,input().split())
  for dx in [-1,0,1]:
    for dy in [-1,0,1]:
      if 2 <= a+dx <H and 2 <= b+dy <W:
        ans[blacks[(a+dx,b+dy)]]-=1
        ans[blacks[(a+dx,b+dy)]+1]+=1
      blacks[(a+dx,b+dy)]+=1
        
for i in range(10): print(ans[i])
### BUGGY CODE ###

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

def kitai(x):
  p = 1/x
  ex = 0
  for i in range(1, x+1):
    px = p*i
    ex += px
  return ex

mem = {}
isum = 0
keys = (0, 0)
for i in range(n):
  if i+k > n:
    break
  temp = p[i:i+k]
  if sum(temp) > isum:
    isum = sum(temp)
    keys = (i, i+k)

print(kitai(isum+(k-1)))


### FIXED CODE ###

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

def kitai(x):
  return (1+int(x))/2

p = list(map(kitai, input().split()))

pre = psum = sum(p[0:k])

for i in range(1, n):
  if i+k > n:
    break
  pre = pre - p[i-1] + p[i+k-1]
  psum = max(psum, pre)

print(psum)
### BUGGY CODE ###

N, M, K = (int(x) for x in input().split())

def cell_dist_sum(i,j):
    x = (i*(i+1)//2+(N-i-1)*(N-i)//2)*M
    y = (j*(j+1)//2+(M-j-1)*(M-j)//2)*N
    return x+y

def nCm(n,m):
    if m < 0 or m > n:
        return 0
    nf = factorial(n)
    nm = factorial(m)
    nm2 = factorial(n-m)
    return (nf//nm//nm2) % 1000000007

def factorial(n):
    ans = 1
    for i in range(n):
        ans *= (i+1)
    return ans

c_sum = 0
for i in range(N):
    for j in range(M):
        c_sum += cell_dist_sum(i,j)
c_sum = c_sum//2
c_sum *= nCm(N*M-2, K-2)
c_sum = c_sum % 1000000007

print(c_sum)


### FIXED CODE ###

import math

N, M, K = (int(x) for x in input().split())

def comb(n,k,p):
    if k < 0 or k > n:
        return 0
    if n == 0 or k == 0:
        return 1
    a=math.factorial(n) % p
    b=math.factorial(k) % p
    c=math.factorial(n-k) % p
    return (a*mypow(b,p-2,p)*mypow(c,p-2,p)) % p

def mypow(a,b,p):
    if b == 0: return 1
    if b % 2 == 0:
        d=mypow(a,b//2,p)
        return d*d % p
    if b % 2 == 1:
        return (a*mypow(a,b-1,p )) % p

c_sum = (M*(N-1)*N*(N+1)*M+N*(M-1)*M*(M+1)*N)//3
c_sum = c_sum//2
c_sum *= comb(N*M-2, K-2, 1000000007)
c_sum = c_sum % 1000000007

print(c_sum)
### BUGGY CODE ###

import sys
from bisect import bisect_left
input = sys.stdin.readline
n = int(input())
xd = [list(map(int,input().split())) for i in range(n)]
mod = 998244353
xd.sort()
go = [[] for i in range(n+1)]
come = [-1 for i in range(n+1)]
deg = [0]*(n+1)
move = [-1]*n
xdsum = [(sum(xd[i]),i) for i in range(n)]
xdsum.sort()
for i in range(n-2,-1,-1):
  for j in range(i+1,n):
    if move[j] != -1:
      continue
    if xd[i][0]+xd[i][1] > xd[j][0]:
      move[j] = i+1
for i in range(n):
  if move[i] == -1:
    continue
  come[i+1] = move[i]
  go[move[i]].append(i+1)
  deg[move[i]] += 1
leafls = []
ans = 1
dp = [1]*(n+1)
for i in range(1,n+1):
  if not go[i]:
    leafls.append(i)
    dp[i] = 2
while leafls:
  x = leafls.pop()
  if come[x] == -1:
    ans = ans*dp[x]%mod
    continue
  y = come[x]
  if deg[y] >= 1:
    deg[y] -= 1
    dp[y] = dp[y]*dp[x]%mod
    if deg[y] == 0:
      dp[y] += 1
      leafls.append(y)
print(ans)

### FIXED CODE ###

import sys
from bisect import bisect_left,bisect_right
input = sys.stdin.readline
ide = 0
def func(a,b):
  return max(a,b)
class SegmentTree:
  def __init__(self,ls,commutative = True):
    if commutative == True:
      self.n = len(ls)
      self.tree = [ide for i in range(self.n)]+ls
    else:
      self.n = 2**((len(ls)-1).bit_length())
      self.tree = [ide for i in range(self.n)]+ls+[ide for i in range(self.n-len(ls))]
    for i in range(1,self.n)[::-1]:
      self.tree[i] = func(self.tree[i<<1|0],self.tree[i<<1|1])
  def getall(self):
    return self.tree[1]
  def get(self,l,r):
    lret = ide
    rret = ide
    l += self.n
    r += self.n
    while l < r:
      if l&1:
        lret = func(lret,self.tree[l])
        l += 1
      if r&1:
        rret = func(self.tree[r-1],rret)
      l >>= 1
      r >>= 1
    ret = func(lret,rret)
    return ret
  def update(self,i,x):
    i += self.n
    self.tree[i] = x
    while i > 1:
      i >>= 1
      self.tree[i] = func(self.tree[i<<1|0],self.tree[i<<1|1])
n = int(input())
xd = [list(map(int,input().split())) for i in range(n)]
mod = 998244353
xd.sort()
xls = list(zip(*xd))[0]
rls = [0]*n
st = SegmentTree(rls)
for i in range(n)[::-1]:
  idx = bisect_left(xls,xd[i][0]+xd[i][1])-1
  x = st.get(i,idx+1)
  st.update(i,max(i,x))
dp = [0]*(n)
dp[-1] = 2
for i in range(n-1)[::-1]:
  x = st.get(i,i+1)
  if x == n-1:
    dp[i] = dp[i+1]+1
  else:
    dp[i] = dp[i+1]+dp[x+1]
  dp[i] %= mod
print(dp[0])
### BUGGY CODE ###

import math


nums = [int(e) for e in input().split()]

a = nums[0]
b = nums[1]
n = nums[2]

max_score = -1
score = -1

for x in range(1, n+1):
    score = math.floor(a*x/b) - a* math.floor(x/b)
    if max_score < score:
        max_score = score

print(max_score)


### FIXED CODE ###

import math


nums = [int(e) for e in input().split()]

a = nums[0]
b = nums[1]
n = nums[2]

max_score = -1
score = -1

# for x in range(1, n+1):
#     score = math.floor(a*x/b) - a* math.floor(x/b)
#     if max_score < score:
#         max_score = score
#     elif x > b:
#         break

if b > n:
    max_score = math.floor(a*n/b)
else:
    max_score = math.floor(a*(b-1)/b)

print(max_score)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
a.append(0)
a.insert(0, 0)
inter = []

for i in range(n+1):
    inter.append(abs(a[i]-a[i+1]))

for j in range(n):
    diff = inter[j]+inter[j+1]-abs(a[j]-a[j+2])
    ans = sum(inter)-diff
    print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a.append(0)
a.insert(0, 0)
inter = []

for i in range(n+1):
    inter.append(abs(a[i]-a[i+1]))

SUM = sum(inter)

for j in range(n):
    diff = inter[j]+inter[j+1]-abs(a[j]-a[j+2])
    ans = SUM-diff
    print(ans)
### BUGGY CODE ###

K=int(input())
def gcd(a,b,c):
    if a <b:
        a,b=b,a
    while a%b != 0:
        a,b= b,a%b
    if b < c:
        b,c=c,b
    while b % c != 0:
        b,c = c,b%c
    return c
x=0
for i in range(1,K+1):
    for j in range(1,K+1):
        for l in range(1,K+1):
            if (i==1) or (j==1) or (l==1):
                x+=1
            elif (j%i==i) or (l%j==j) or(l%i==i):
                x+=1
            else:
                x += gcd(i,j,l)
print(x)


### FIXED CODE ###

K=int(input())
def gcd(a,b,c):
    if a <b:
        a,b=b,a
    while a%b != 0:
        a,b= b,a%b
    if b < c:
        b,c=c,b
    while b % c != 0:
        b,c = c,b%c
    return c
x=0
for i in range(1,K+1):
    for j in range(1,K+1):

            for l in range(1,K+1):
                
                    if (i==1) or (j==1) or (l==1):
                        x+=1
                    else:
                        x += gcd(i,j,l)
print(x)
### BUGGY CODE ###

N = int(input())
 
A = list(map(int,input().split()))
 
A = sorted(A)[0:2]
 
INF = 10 ** 9

for i in range(0,INF):
	A[1] % A[1] - A[0]
	if A[1] < A[0]:
		A[1],A[0] = A[0],A[1]
	if A[0] <= 0:
		break
		
if A[0] == 1:
	print(1)
else:print(A[1])

### FIXED CODE ###

import fractions
from functools import reduce

def gcd(numbers):
    return reduce(fractions.gcd, numbers)

N = int(input())

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

print(gcd(A))
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
over_value = 10 ** 18 + 1
total = 1
cnt = 0
while cnt < N:
    total *= A[cnt]
    if total >= over_value:
        total = -1
    cnt += 1
    
for i in range(N):
    if A[i] == 0:
        total = 0
print(total)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
over_value = 10 ** 18
total = 1
cnt = 0
while cnt < N:
    total *= A[cnt]
    if total > over_value:
        total = -1
        break
    cnt += 1
    
for i in range(N):
    if A[i] == 0:
        total = 0
print(total)
### BUGGY CODE ###

N = int(input())
a = list(map(int, list(input())))
x = [max(a[i], a[i+1]) - min(a[i], a[i+1]) for i in range(N-1)]

def make_x(l):
	n = len(l)
	if n == 1:
		return l
	l2 = [l[0]]
	cnt = 1
	length = 1
	for i in range(1, n):
		if l[i] != l2[-1]:
			if cnt % 2 == 0:
				l2.append(l2[-1])
			cnt = 1
			l2.append(l[i])
			length += 1
		else:
			cnt += 1
	if length == 1:
		return [0]
	return l2

def next_x(l):
	n = len(l)
	return [max(l[i], l[i+1]) - min(l[i], l[i+1]) for i in range(n-1)]

while len(x) > 1:
	x = make_x(next_x(x))
print(x[0])

### FIXED CODE ###

N = int(input())
a = list(map(int, list(input())))
t = [0 for i in range(N+1)]
i = 2
while i < N:
	for j in range(i, N+1, i):
		t[j] += 1
	i *= 2
sum_t = [0]
for i in range(1, N+1):
	sum_t.append(sum_t[-1] + t[i])

x = [max(a[i], a[i+1]) - min(a[i], a[i+1]) for i in range(N-1)]


def isCombOdd(n,k):
	bunshi = sum_t[n] - sum_t[n-k]
	bunbo = sum_t[k]
	return bunshi == bunbo

f1 = False
for n in x:
	if n == 1:
		f1 = True
		break
if f1:
	x = [n if n != 2 else 0 for n in x]

candidate = 1 if f1 else 2
ans = 0
for i in range(N-1):
	if x[i] > 0 and isCombOdd(N-2, i):
		ans = 1 - ans

print(0 if ans == 0 else candidate)
### BUGGY CODE ###

n,w=list(map(int,input().split()))
k=[]
for i in range(n):
    k.append(list(map(int,input().split())))
vn=max([k[i][1] for i in range(n)])*n
dp=[[0]+[float("inf") for i in range(vn)] for i in range(n+1)]
for i in range(1,n+1):
    for j in range(1,vn+1):
        if j<=k[i-1][1]:
            dp[i][j]=min(dp[i-1][j],k[i-1][0])
        else:
            dp[i][j]=min(dp[i-1][j],k[i-1][0]+dp[i-1][j-k[i-1][1]])
for i in range(vn,-1,-1):
    if dp[n][i]<=w:
        print(i)
        break

### FIXED CODE ###

n,w=list(map(int,input().split()))
k=[]
for i in range(n):
    k.append(list(map(int,input().split())))
dp=[[0 for i in range(w+1)] for i in range(n+1)]
for i in range(1,n+1):
    for j in range(1,w+1):
        if j<k[i-1][0]:
            dp[i][j]=dp[i-1][j]
        else:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-k[i-1][0]]+k[i-1][1])
print(dp[n][w])
### BUGGY CODE ###

n,m = map(int,input().split())
a_list = []
li = []

for i in range(m):
    a,b = map(int,input().split())
    a_list.append(a)
    c = list(map(int,input().split()))
    for j in range(b):
        c[j] -= 1
    li.append(c)

min_coin = 10**10

for i in range(2**m):
    bool_list = [False]*n
    coin = 0
    for j in range(m):
        if (i >> j)&1:
            for k in li[j]:
                bool_list[k] = True
            coin += a_list[j]
    if False in bool_list:
        continue
    min_coin = min(min_coin,coin)

if min_coin == 10**10:
    print(-1)
else:
    print(min_coin)

### FIXED CODE ###

n,m = map(int,input().split())
a_list = []
c = []

for i in range(m):
    a,b = map(int,input().split())
    a_list.append(a)
    c.append(sum(1 << j-1 for j in list(map(int,input().split()))))

inf = 10**10
dp = [inf]*(1 << n)
dp[0] = 0

for i in range(1 << n):
    for j in range(m):
        dp[c[j]|i] = min(dp[c[j]|i],dp[i]+a_list[j])

if dp[-1] == inf:
    print(-1)
else:
    print(dp[-1])
### BUGGY CODE ###

#!/usr/bin/python
import sys
#if sys.version_info[0]>=3:raw_input=input

from scipy.sparse import*
g=[]
n=int(raw_input())
for _ in xrange(n-1):
	a,b=map(int,raw_input().split())
	g+=[(a-1,b-1,1)]
z=[-1]*n
for _ in xrange(int(raw_input())):
	a,b=map(int,raw_input().split())
	g+=[(n,a-1,b)]
	z[a-1]=b
a,b,c=zip(*g)
a=map(int,csgraph.dijkstra(csr_matrix((c,(a,b)),[n+1]*2),0,n))
for i in xrange(n):
	if z[i]>=0 and z[i]!=a[i]:
		print('No')
		sys.exit()
for e in g:
	if e[0]<e[1] and abs(a[e[0]]-a[e[1]])!=1:
		print('No')
		sys.exit()
print('Yes')
print("\n".join(map(str,a[:n])))

### FIXED CODE ###

#!/usr/bin/python
def shortestPath(g,s,dist,prev):
	n = len(g)-1
	Q=[]
	heapq.heappush(Q,(0,-2,s))
	while Q:
		e = heapq.heappop(Q)
		if prev[e[2]]!=-1: continue
		prev[e[2]] = e[1]
		for f in g[e[2]]:
			if dist[f[2]] > e[0] + f[0]:
				dist[f[2]] = e[0] + f[0]
				heapq.heappush(Q,(e[0]+f[0],f[1],f[2]))

import sys,heapq
#if sys.version_info[0]>=3:raw_input=input

n=int(raw_input())
g=[[] for _ in range(n+1)]
for _ in xrange(n-1):
	a,b=map(int,raw_input().split())
	g[a-1]+=[(1,a-1,b-1)]
	g[b-1]+=[(1,b-1,a-1)]
z=[-1]*n
for _ in xrange(int(raw_input())):
	a,b=map(int,raw_input().split())
	g[n]+=[(b,n,a-1)]
	z[a-1]=b
a=[1e9]*n+[0]
shortestPath(g,n,a,[-1]*(n+1))
for i in xrange(n):
	if z[i]>=0 and z[i]!=a[i]:
		print('No')
		sys.exit()
for _ in g:
	for e in _:
		if e[1]<e[2] and abs(a[e[1]]-a[e[2]])!=1:
			print('No')
			sys.exit()
print('Yes')
print("\n".join(map(str,a[:n])))
### BUGGY CODE ###

# sys.stdin.readline()
import sys
input = sys.stdin.readline

from itertools import accumulate
n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(n):
    ans += list(accumulate(a[i:])).count(0)
print(ans)

### FIXED CODE ###

import sys
import itertools
from collections import Counter
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
cumsum = itertools.accumulate([0] + a)
counter = Counter(cumsum)
ans = 0

for value in counter.values():
    ans += value * (value - 1) // 2

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

S = input()
len_ini_S = len(S)
tmp_len_rep_S = len_ini_S

while True:
  rep_S = S.replace('01','').replace('10','')
  len_rep_S = len(rep_S)
  if tmp_len_rep_S == len_rep_S:
    break
  else:
    tmp_len_rep_S = len_rep_S
    S = rep_S
    

print(len_ini_S - len_rep_S)

### FIXED CODE ###

s_list = [int(s) for s in input()]

if s_list.count(0) < s_list.count(1):
  print(s_list.count(0) * 2)
else:
  print(s_list.count(1) * 2)
### BUGGY CODE ###

N,C = map(int,input().split())
tv_times = [[int(j) for j in input().split()] for i in range(N)]

channells = {}
for i in range(C+1):
    channells[i] = []
max_end = -1

for i in range(N):
    s,g,c = tv_times[i]
    max_end = max(max_end,g)
    channells[c] += [s,g]

tv_times = []
f = [0 for i in range(max_end+1)]
for cha in channells.keys():
    remove_list = []
    time = channells[cha]
    time.sort()
    for i in range(len(time)//2-1):
        if time[2*i+1] == time[2*i+2]:
            remove_list.append(time[2*i+1])
    for i in range(len(remove_list)):
        time.remove(remove_list[i])
        time.remove(remove_list[i])
    # print(time)
    # print(f)
    for i in range(len(time)//2):
        f[max(time[2*i]-1,0)] += 1
        f[time[2*i+1]] -= 1

ans = -1
for i in range(1,max_end):
    f[i] += f[i-1]
    if ans < f[i]:
        ans = f[i]

# print(f)
print(ans)


### FIXED CODE ###

N,C = map(int,input().split())
tv_times = [[int(j) for j in input().split()] for i in range(N)]

channells = {}
for i in range(C+1):
    channells[i] = []
max_end = -1

for i in range(N):
    s,g,c = tv_times[i]
    max_end = max(max_end,g)
    channells[c] += [s,g]

tv_times = []
f = [0 for i in range(max_end+1)]
for cha in channells.keys():
    remove_list = []
    time = channells[cha]
    time.sort()
    for i in range(1,len(time)-1):
        if time[i] == time[i+1]:
            remove_list.append(time[i])
    time = list(set(time)-set(remove_list))
    time.sort()
    for i in range(len(time)//2):
        f[max(time[2*i]-1,0)] += 1
        f[time[2*i+1]] -= 1
ans = -1
for i in range(1,max_end+1):
    f[i] += f[i-1]
    if ans < f[i]:
        ans = f[i]

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

n = int(input())
s = [input() for i in range(n)]

def yoi(s, b):
  for i in range(n):
    for j in range(i):
      if s[i][(j + b) % n] != s[j][(i + b) % n]:
        return 0
  return 1

def not_eq(s, b, n, i, j):
  return s[i][(j + b) % n] != s[j][(i + b) % n]

def yoi2(s, b):
  if sum(not_eq(s, b, n, i, j) for i in range(n) for j in range(i)) > 0:
        return 0
  return 1

sol = n * sum(yoi2(s, b) for b in range(n))
print(sol)

### FIXED CODE ###

n = int(input())
s = [input() for i in range(n)]
st = [str().join(s_) for s_ in zip(*s)]

sol = 0

for i in range(n):
    for k in range(n):
        if s[k] != st[k]:
            break
    else:
        sol += 1
    
    s = [s_l[1:]+s_l[0] for s_l in s]
    st = st[1:] + [st[0]]
    
print(sol * n)