Harryxun/stf_run huggingface dataset:
def calc_state_number(stair_num, now_stair, damaged_step_list, memo):
    # print(str(now_stair) + '/' + str(stair_num))
    if memo[now_stair-1] != -1:
        return memo[now_stair-1]
    if now_stair in damaged_step_list:
        memo[now_stair-1] = 0
        return memo[now_stair-1]
    if now_stair > stair_num:
        return 0
    if now_stair == stair_num:
        memo[now_stair-1] = 1
        return memo[now_stair-1]
    memo[now_stair-1] = (calc_state_number(stair_num, now_stair+1, damaged_step_list, memo) + calc_state_number(stair_num, now_stair+2, damaged_step_list, memo))%1000000007
    return memo[now_stair-1]

if __name__ == '__main__':
    N, M = map(int, input().split())
    a = [int(input()) for _ in range(M)]
    a = sorted(a)

    memo = [-1] * (N+2)

    answer = 1
    if a[-1::] == N:
        answer = 0

    for i in range(1, M):
        if a[i-1] + 1 == a[i]:
            answer = 0

    if answer != 0:
        answer = calc_state_number(N, 0, a, memo)
    
    print(answer)
    

### FIXED CODE ###

if __name__ == '__main__':
   n, m = map(int,input().split())
   a = set([int(input()) for i in range(m)])

   MOD = 1000000007

   dp = [0 for i in range(n+1)]
   dp[0] = 1
   if 1 in a:
      dp[1] = 0
   else:
      dp[1] = 1

   for i in range(2,n+1):
      if (i-1 in a) and (i-2 in a):
         dp[i] = 0
      elif i-1 in a:
         dp[i] = dp[i-2] % MOD
      elif i-2 in a:
         dp[i] = dp[i-1] % MOD
      else:
         dp[i] = (dp[i-1] + dp[i-2]) % MOD

   print(dp[n])
N = int(input())
if int(N[0]) == 7, or int(N[1]) == 7, int(N[2]) == 7:
  print('Yes')
else:
  print('No')


### FIXED CODE ###

N = input()
if '7' in N:
  print('Yes')
else:
  print('No')
n, m = map(int, input().split())
d = [[] for i in range(n)]    


for _ in range(m):
    p, s = input().split()
    p = int(p) - 1
    d[p].append(s)

ac_cnt, w_cnt = 0, 0
for l in d:
    if len(l) != 0:
        w_cnt += l.index("AC")

    if "AC" in l:
        ac_cnt += 1

print(ac_cnt, w_cnt)


### FIXED CODE ###

n, m = map(int, input().split())
d = [[] for i in range(n)]    


for _ in range(m):
    p, s = input().split()
    p = int(p) - 1
    d[p].append(s)

ac_cnt, w_cnt = 0, 0
for l in d:
    if len(l) != 0 and "AC" in l:
        w_cnt += l.index("AC")

    if "AC" in l:
        ac_cnt += 1

print(ac_cnt, w_cnt)
r, g, b = input().split()

n = r + g + b

print("YES" if n % 4 == 0 else "NO")

### FIXED CODE ###

r, g, b = input().split()

n = int(r + g + b)

print("YES" if n % 4 == 0 else "NO")
# -*- coding: utf-8 -*-
from collections import deque
from heapq import heappush, heappop, heapify, merge
from collections import defaultdict
import sys
sys.setrecursionlimit(10**5)
def inpl(): return tuple(map(int, input().split()))
 
N, M = inpl()
A = inpl()
tree = [[-1, 1]  for _ in range(N)]# [next, rank]

def find(i):
    if tree[i][0] == -1:
        group = i
    else:
        group = find(tree[i][0]) 
        tree[i][0] = group
    return group
  
def unite(x, y):
    px = find(x)
    py = find(y)
      
    if tree[px][1] == tree[py][1]: # rank is same
        tree[py][0] = px
        tree[px][1] += 1
    else:
        if tree[px][1] < tree[py][1]:
            px, py = py, px
        tree[py][0] = px
  
for _ in range(M):
    x, y = tuple(map(int, input().split()))
    if not int(find(x) == find(y)):
        unite(x, y)

D = defaultdict(list)
for n in range(N):
    D[find(n)].append(A[n])

H = []
S = deque([]) # single
for k, v in D.items():
    if len(v) == 1:
        S.append(v)
    else:
        H.append(sorted(v))

heapify(H)

res = 0 
while True:
    if (len(H) == 0) or (len(S) + len(H) <= 1):
        break
    
    if len(S) > 1:
        A = S.leftpop()
    else:
        if len(H) <= 1:
            break
        A = heappop(H)

    B = heappop(H)

    res += A[0] + B[0]
    C = list(merge(A[1:], B[1:]))

    if len(C) == 1:
        S.append(C)
    elif len(C) == 0: # ありえないはず
        pass
    else:
        heappush(H, C)

ok = True
if len(S) > 2:
    print("Impossible")
    ok = False
elif len(S) == 2:
    res += S[0]+S[1]
elif len(S) == 1:
    A = S[0]
    if len(H) == 1:
        B = heappop(H)
        res += A[0] + B[0]
else:
    pass
if ok:
    print(res)

### FIXED CODE ###

# -*- coding: utf-8 -*-
from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
def inpl(): return tuple(map(int, input().split()))
 
N, M = inpl()
A = inpl()
tree = [[-1, 1]  for _ in range(N)] # [next, rank]
 
def find(i):
    if tree[i][0] == -1:
        group = i
    else:
        group = find(tree[i][0]) 
        tree[i][0] = group
    return group
  
def unite(x, y):
    px = find(x)
    py = find(y)
      
    if tree[px][1] == tree[py][1]: # rank is same
        tree[py][0] = px
        tree[px][1] += 1
    else:
        if tree[px][1] < tree[py][1]:
            px, py = py, px
        tree[py][0] = px
  
for _ in range(M):
    x, y = tuple(map(int, input().split()))
    if not int(find(x) == find(y)):
        unite(x, y)
 
D = defaultdict(list)
for n in range(N):
    D[find(n)].append(A[n])
 
H = []
res = 0 

for k, v in D.items():
    v = sorted(v)
    res += v[0]
    H.extend(v[1:])
 
if N < 2*(N-M-1):
    print("Impossible")
elif M == N-1:
    print(0)
else:
    res += sum(sorted(H)[:2*(N-M-1) - len(D.keys())])
    print(res)
s = str(N)
if s.count("7")>0:
	print(True)
else:
	print(False)

### FIXED CODE ###

a = input()

if a.count("7")>0:
	print("Yes")
else:
	print("No")
a,b=map(int,input().split())
if a==b:
    print(a)
else:
    s=0
    t=0
    for i in range(41):
        if 2**i>a:
            s=i
            break
    for i in range(41):
        if 2**i>b:
            t=i-1
            break
    ans=0
    for j in range(a,2**s):
        ans=ans^j
    for j in range(2**t,b+1):
        ans=ans^j
print(ans)

### FIXED CODE ###

a,b=map(int,input().split())
if a==b:
    print(a)
else:
    s=4-a%4
    t=(1+b%4)
    ans=0
    for j in range(a,a+s):
        ans=ans^j
    for j in range(b+1-t,b+1):
        ans=ans^j
    print(ans)
#B - Substring 
S = str(input())
T = str(input())
i = 0
j = 0

k = len(S)
l = len(T)
change_min = l

for i in range(l):
    for m in range(l - i) :
        change = l
        for j in range(k - (l -i)+1):
            print(S[j+m:j +l-i],T[m:l-i],change,l-i-m)
            if S[j+m:j +l-i] == T[m:l-i]:
                print('Match !!')
                change -= l-i-m
        if change_min > change:
            change_min = change
# 出力
print(change_min)


### FIXED CODE ###

#B - Substring 
S = str(input())
T = str(input())
i = 0
j = 0

Slen = len(S)
Tlen = len(T)
change_min = Tlen

for i in range(Slen - Tlen + 1):
    diff = 0
    for j in range(Tlen):
        if T[j] != S[i + j]:
            diff += 1
    change_min = min(change_min,diff)

# 出力
print(change_min)
n=int(input())
a=list(map(int,input().split()))
l=0
for i in range(n):
  if a[i]%2==0:
    l.append(a[i])
for j in range(len(l)):
  if l[j]%3==0 or l[j]%5==0:
    l.remove(l[j])
if len(l)==0:
  print('APPROVED')
else:
  print('DENIED')
  
  

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
count=0
for i in range(n):
  if a[i]%2==0:
    if a[i]%3==0 or a[i]%5==0:
      pass
    else:
      count+=1
if count==0:
  print('APPROVED')
else:
  print('DENIED')
a, b, c = map(int, input().split())
x =a*10 + b
y = b*10+ c
print([x, y][if x < y])


### FIXED CODE ###

a, b, c = map(int, input().split())
x = a*10 + b + c
y = b*10+ c + a
z = c*10+ a + b
print(max([x, y,z]))
n,m = map(int,input().split())
branch = list(tuple(map(int,input().split())) for i in range(m))
que = range(n)
flag = -1
friend = [{1}]

for a,b in branch:
    for i in range(len(friend)):
        if (a in friend[i]) or (b in friend[i]):
            friend[i].add(a)
            friend[i].add(b)
            if flag >= 0:
                friend[flag] = friend[flag]|friend[i]
                friend.pop(i)
            flag = i
    if flag == -1:
        friend.append({a,b})
    else: flag = -1

print(friend)
len_friend = list(len(i) for i in friend)
print(max(len_friend))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10000000)

class Graph:
    def __init__(self,n,side):
        self.side = side
        self.neighbor = [set() for i in range(n+1)]
        self.visited = [False]*(n+1)
        self.group =[0]*n
        self.product()
    def product(self):
        for a,b in self.side:
            self.neighbor[a].add(b)
            self.neighbor[b].add(a)
    def dfs(self,x,a):
        self.group[a] += 1
        self.visited[x] = True
        for i in self.neighbor[x]:
            if self.visited[i]:continue
            self.dfs(i,a)
    def all_dfs(self):
        a = 0
        for i in range(1,n+1):
            if not self.visited[i]:
                self.dfs(i,a)
                a += 1

n,m = map(int,input().split())
side = list(tuple(map(int,input().split()))for i in range(m))
graph1 = Graph(n,side)
graph1.all_dfs()
print(max(graph1.group))
from collections import deque
import copy
f = open("C:/Users/naoki/Desktop/Atcoder/input.txt") 

n = int(f.readline())
p = list(map(int, f.readline().split()))
for i in range(len(p)):
    p[i] -= 1

to_outsides = [[0 for _ in range(n)] for _ in range(n)]
not_exist = [["■" for _ in range(n)] for _ in range(n)]


for i in range(n):
    for j in range(n):
        to_outside = [i,n-1-i,j,n-1-j]
        to_outsides[i][j] = min(to_outside)

directions = [[-1,0],[1,0],[0,-1],[0,1]]

all_loss = 0
answer = 0
for i, person in enumerate(p):
    to_outsides_pre = copy.deepcopy(to_outsides)    
    exited = [person//n, person%n]
    answer += to_outsides[exited[0]][exited[1]]
    not_exist[exited[0]][exited[1]] = "□"
    seen = []
    seen.append([exited[0],exited[1]])
    todo = deque([exited])
    renews = []
    while len(todo)>0:
        now = todo.pop()
        renews.append(now)
        for direction in directions:
            try:
                checking = [now[0]+direction[0],now[1]+direction[1]]
                to_outsides[checking[0]][checking[1]]
            except:
                continue
            if [checking[0],checking[1]] not in seen and\
            ((not_exist[checking[0]][checking[1]] == "□" and  to_outsides[checking[0]][checking[1]]==to_outsides[now[0]][now[1]])or\
            to_outsides[checking[0]][checking[1]]>to_outsides[now[0]][now[1]]):
                todo.append([checking[0],checking[1]])
                seen.append([checking[0],checking[1]])
    
    for renew in renews:
        if to_outsides[renew[0]][renew[1]] != 0:
            to_outsides[renew[0]][renew[1]]-=1
print(answer)

### FIXED CODE ###

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

dp = [[min(i, N - i - 1, j, N - j - 1) for j in range(N)] for i in range(N)]

presence = [[1 for j in range(N)] for i in range(N)]

ans = 0
for i in range(len(P)):
    P[i] -= 1
    x, y = divmod(P[i], N)
    ans += dp[x][y]
    presence[x][y] = 0

    Q = [(x, y)]
    #%%
    while Q:
        x, y = Q.pop()
        new_value = dp[x][y] + presence[x][y]
        if 1 <= x and dp[x - 1][y] > new_value:
            dp[x - 1][y] = new_value
            Q.append((x - 1, y))
        if x < N - 1 and dp[x + 1][y] > new_value:
            dp[x + 1][y] = new_value
            Q.append((x + 1, y))
        if 1 <= y and dp[x][y - 1] > new_value:
            dp[x][y - 1] = new_value
            Q.append((x, y - 1))
        if y < N - 1 and dp[x][y + 1] > new_value:
            dp[x][y + 1] = new_value
            Q.append((x, y + 1))

print(ans)
N,L=map(int,input().split())
List = []
for i in range (N):
  List.append(int(input()))
List.sort()
res = ""
for i in range(N):
  res+=List[i]
print(res)

### FIXED CODE ###

N,L=map(int,input().split())
List = []
for i in range (N):
  List.append(str(input()))
List.sort()
res = ""
for i in range(N):
  res+=List[i]
print(res)
# -*- coding: utf-8 -*-
"""
Created on Sun Mar 22 21:08:11 2020

@author: azikausy
"""


from scipy.special import comb
n, m = map(int, input().split())
print(int(comb(n,2)+comb(m,2)))

### FIXED CODE ###

from scipy.misc import comb
n, m = map(int, input().split())
print(comb(n, 2, exact=True)+comb(m, 2, exact=True))
import numpy as np

W, H, x, y = [int(x) for x in input().split(" ")]
max_area =  W * H / 2.0
eps = 1e-6
if x + x = W and y + y == H:
    flag = 1
else:
    flag = 0

print(max_area, flag) 

### FIXED CODE ###

import numpy as np
from fractions import gcd

def lcm(x, y):
    return x * y // gcd(x, y)
A, B, C, D = [int(x) for x in input().split(" ")]
n_targets = B - A + 1

n_compC = n_targets - (B // C - (A - 1) // C)
n_compD = n_targets - (B // D - (A - 1) // D)
n_compCandD = n_targets - (B // lcm(C, D) - (A - 1) // lcm(C, D))

print(n_compC + n_compD - n_compCandD)
N,Y = map(int, input().split())

for j in range(N+1):
    for i in range(N+1):
        sum = 10000*j + 5000*i + 1000*(N-i-j)
        if(sum==Y and N-i-j>=0):
            print(j,i,N-i-j)
            exit()
            
print('-1 -1 -1')

### FIXED CODE ###

date = input()

date_list = list(date)
date_list[3] = '8'
output = ''.join(date_list)

print(output)
import sys


def input(): return sys.stdin.redline().strip()


N, M = (list)(map(int, input().split()))
edge = []

for _ in range(M):
    edge.append((list)(map(int, input().split())))


inf = 10**15

d = [inf]*(N+1)
d[1] = 0
ans = inf
for i in range(N):
    update = False
    for a, b, c in edge:
        c = -c
        new_d = d[a]+c
        if d[a] != inf and d[b] > new_d:
            d[b] = new_d
            update = True

    if not update:
        break

neg = [False]*(N+1)
for i in range(N):
    for a, b, c in edge:
        c = -c
        new_d = d[a]+c
        if d[a] != inf and d[b] > new_d:
            d[b] = new_d
            neg[b] = True
        if neg[a]:
            neg[b] = True

if neg[-1]:
    print('inf')
else:
    print(-d[-1])


### FIXED CODE ###

import sys


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


N, M = (list)(map(int, input().split()))
edge = []

for _ in range(M):
    edge.append((list)(map(int, input().split())))


inf = 10**15

d = [inf]*(N+1)
d[1] = 0
ans = inf
for i in range(N):
    update = False
    for a, b, c in edge:
        c = -c
        new_d = d[a]+c
        if d[a] != inf and d[b] > new_d:
            d[b] = new_d
            update = True

    if not update:
        break

neg = [False]*(N+1)
for i in range(N):
    for a, b, c in edge:
        c = -c
        new_d = d[a]+c
        if d[a] != inf and d[b] > new_d:
            d[b] = new_d
            neg[b] = True
        if neg[a]:
            neg[b] = True

if neg[-1]:
    print('inf')
else:
    print(-d[-1])
n, h = map(int, input().split())
a, b = [], []
for _ in range(n):
    ai, bi = map(int, input().split())
    a.append(ai), b.append(bi)
a.sort(), b.sort()

ans, amax = 0, a[-1]
for bi in b[::-1]:
    if bi <= amax or h <= 0:
        mod = (h + amax - 1) // amax
        break
    h -= bi
    ans += 1
print(ans + mod if h > 0 else ans)


### FIXED CODE ###

n, h = map(int, input().split())
a, b = [], []
for _ in range(n):
    ai, bi = map(int, input().split())
    a.append(ai), b.append(bi)
a.sort(), b.sort()

ans, amax = 0, a[-1]
for bi in b[::-1]:
    if bi <= amax:
        print(ans + h // amax + (h % amax > 0))
        break
    if h <= 0:
        print(ans)
        break
    h -= bi
    ans += 1
else:
    print(ans + h // amax + (h % amax > 0))
import math
n, d= (int(c) for c in input().split())

x = []

for i in range(n): 
    x.append(input().split())

sum_ans = 0
count=0
for j in range(0,n):
    for k in range(j+1,n-1):
        for n in range(d):
            sum_ans = sum_ans+(x[j][n] - x[k][n]) **2
        if math.sqrt(sum_ans)%1==0:
            count=count+1
        sum_ans=0
print(sum_ans)

### FIXED CODE ###

import math
n, d= (int(c) for c in input().split())

x = []

for i in range(n): 
    x.append(input().split())

sum_ans = 0
count=0
print
for j in range(0,n-1):
    for k in range(j+1,n):
        for l in range(d):
            sum_ans = sum_ans+(int(x[j][l]) - int(x[k][l])) **2
        if math.sqrt(sum_ans)%1==0.0:
            count=count+1
        sum_ans=0
print(count)
nums=str(input())
arr=list(map(int,nums))
l=len(arr)
a=0
i=0
while i<len(arr)-1:
    if arr[i]!=arr[i+1]:
        del arr[i:i+2]
        #print(arr)
        a+=2
        i-=2
    i+=1
print(a)

### FIXED CODE ###

nums=str(input())
arr=list(map(int,nums))
l=len(arr)
a=0
i=0
while i<len(arr)-1:
    if i<0:
        i=0
    if arr[i]!=arr[i+1]:
        del arr[i:i+2]
        #print(arr)
        a+=2
        i-=2
    i+=1
print(a)
from collections import deque

k = int(input())
q = deque(range(1, 10))

for i in range(k-1):
    # popをk-1回やる
    x = q.popleft()
    y = int(str(x)[-1])
    if y-1 >= 0:
        print(int(str(x)+str(y-1)))
        q.append(int(str(x)+str(y-1)))
    q.append(int(str(x)+str(x)[-1]))
    if y+1 < 10:
        q.append(int(str(x)+str(y+1)))

    print(q)




### FIXED CODE ###

from collections import deque

k = int(input())
q = deque(range(1, 10))

for i in range(k-1):
    # popをk-1回やる
    x = q.popleft()
    y = int(str(x)[-1])
    if y-1 >= 0:
        q.append(int(str(x)+str(y-1)))
    q.append(int(str(x)+str(x)[-1]))
    if y+1 < 10:
        q.append(int(str(x)+str(y+1)))

print(q[0])
import bisect
A, B, Q = map(int, input().split())
INF = 10 ** 18
s = [-INF] + [int(input()) for i in range(A)] + [INF]
t = [-INF] + [int(input()) for i in range(B)] + [INF]
for q in range(Q):
  x = int(input())
  b, d = bisect.bisect_right(s, x), bisect.bisect_right(t, x)
  res = INF
  for S in [s[b - 1], s[b]]:
  for T in [t[d - 1], t[d]]:
  d1, d2 = abs(S - x) + abs(T - S), abs(T - x) + abs(S - T)
  res = min(res, d1, d2)
  print(res)

### FIXED CODE ###

import bisect
A, B, Q = map(int, input().split())
INF = 10 ** 18
s = [-INF] + [int(input()) for i in range(A)] + [INF]
t = [-INF] + [int(input()) for i in range(B)] + [INF]
for q in range(Q):
    x = int(input())
    b, d = bisect.bisect_right(s, x), bisect.bisect_right(t, x)

    res = INF
    for S in s[b-1:b+1]:
        for T in t[d-1:d+1]:
            d1, d2 = abs(S - x) + abs(T - S), abs(T - x) + abs(S - T)
            res = min(res, d1, d2)
    print(res)
n = int(input())
l=[]
for i in range(n-1):
    tmp = list(map(int,input().split()))
    l.append(tmp)
l.sort()

from collections import deque
Q = deque()
Q.append(0)

dis = [0]*n
dis[0]=0

while Q:
    num=Q.popleft()

    for tmp in l:
        if tmp[0]-1 == num:
            nxt=tmp[1]-1
            Q.append(nxt)
            dis[nxt] = dis[num] + tmp[2]

for a in dist:
    print(a%2)

### FIXED CODE ###

n = int(input())
l=[]
for i in range(n-1):
    tmp = list(map(int,input().split()))
    l.append(tmp)
l.sort()

link = [[] for _ in range(n)]

for tmp in l:
    link[tmp[0]-1].append([tmp[1]-1,tmp[2]])
    link[tmp[1]-1].append([tmp[0]-1,tmp[2]])

from collections import deque
Q = deque()
Q.append(0)

dis = [-1]*n
dis[0]=0

while Q:
    num=Q.popleft()
    for tmp in link[num]:
        if dis[tmp[0]] == -1:
            dis[tmp[0]] = dis[num]+tmp[1]
            Q.append(tmp[0])

for a in dis:
    print(a%2)
import numpy as np

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)


K = int(input())
sum = 0
ijkrange = np.arange(1, K+1)

for i in ijkrange:
    for j in ijkrange:
        for l in ijkrange:
            sum += gcd(i, gcd(j, l))

print(sum)

### FIXED CODE ###

import math

K = int(input())
sum = 0

for i in range(1, K+1):
    for j in range(1, K+1):
        for l in range(1, K+1):
            sum += math.gcd(i, math.gcd(j, l))

print(sum)
H, N = map(int, input().split())
lis = list(map(input().split()))
if sum(lis) >= H:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

H, N = map(int, input().split())
lis = list(map(int, input().split()))
if sum(lis) >= H:
  print("Yes")
else:
  print("No")
n = int(input())
A = input().split()
for i in range(len(A)) :
    A[i] = int(A[i])
print(max(A)-min(A))

### FIXED CODE ###

N = int(input())

if N % 2 == 0 :
    print(N)
else :
    print(N * 2)
s = list(map(int, input().split()))
n,m = s[0],s[1]
a = [int(input()) for i in range(m)]



if n == 1:
    print(1)

elif n == 2:
    if m == 0:
        print(2)
    elif m == 1:
        if a[0] == 2:
            print(0)
        else:
            print(1)
        
    
elif n == a[-1]:
    print(0)
    
else:
    if m == 0:
        t = -1
    else:
        c = 0
        t = a[c]-1
    x, y = 0, 1
    for i in range(n):
        if x == 0 and y == 0:
            break
        elif i == t:
            x, y = y, 0
            if a[c]-1 == a[-1]-1:
                continue
            else:
                c += 1
                t = a[c]-1
        else:
            x, y = y, x + y
    print(y%1000000007)

### FIXED CODE ###

x = list(map(int, input().split()))
x.sort()
print(x[0]+x[1])
#include <iostream>
#include <vector>

int main() {
    vector<vector<int>> vec(100, vector<int>(100, 0));
    cin >> vec.at(100).at(99);
    cout << vec.at(100).at(100) << endl;
}


### FIXED CODE ###

y = int(input())
print(y*y*y)
N=int(input().strip())
a=[0]*(N-1) # # of lines
b=[0]*(N-1)
#to=[[] for j in range(N-1)] # points
ans=[0]*(N-1)

class data:
    def __init__(self):
        self.to=[[] for j in range(N)] # N points
        self.id=[[] for j in range(N)] # N points

data=data()
for i in range(len(a)):
    a,b=list(map(int,input().strip().split()))
    a-=1
    b-=1
    data.to[a].append(b)
    data.id[a].append(i) # index of the line
    data.to[b].append(a)
    data.id[b].append(i)

#print(data.to)
def dfs(v,p,c_p): # vertices & parent idx & color from parent
    lst=data.to[v] # children list
    c=1
    for i,child in enumerate(lst):
        if child==p:
            continue
#        print('vertices=',v)
#        print('child=',child)
#        print('parent=',p)
        if c_p==c:
            c+=1
        ans[data.id[v][i]]=c
        dfs(child,v,c)
        c+=1

dfs(0,-1,-1)
print(max(ans))
for i in range(len(ans)):
    print(ans[i])


### FIXED CODE ###

import sys #追加
sys.setrecursionlimit(500*500) #追加

N=int(input().strip())
a=[0]*(N-1) # # of lines
b=[0]*(N-1)
#to=[[] for j in range(N-1)] # points
ans=[0]*(N-1)

class data:
    def __init__(self):
        self.to=[[] for j in range(N)] # N points
        self.id=[[] for j in range(N)] # N points

def dfs(v,p,c_p): # vertices & parent idx & color from parent
    lst=data.to[v] # children list
    c=1
    for i,child in enumerate(lst):
        if child==p:
            continue
        if c_p==c:
            c+=1
        ans[data.id[v][i]]=c
        c+=1
        dfs(child,v,c-1)

data=data()
for i in range(len(a)):
    a,b=list(map(int,input().strip().split()))
    a-=1
    b-=1
    data.to[a].append(b)
    data.id[a].append(i) # index of the line
    data.to[b].append(a)
    data.id[b].append(i)

#print(data.to)

dfs(0,-1,-1)
print(max(ans))
for i in range(len(ans)):
    print(ans[i])
A = input().split()
count = 0
flag = True

while flag:
  for i in range(N):
    if A[i] % 2 != 0:
      flag = False
      break
  if !flag:
    print(count)
  count += 1
  for i in range(N):
    A[i] = A[i] / 2

### FIXED CODE ###

N = int(input())
A = [int(s) for s in input().split()]
count = 0
flag = True

while flag:
  for i in range(N):
    if A[i] % 2 != 0:
      flag = False
      break
  if flag == False:
    print(count)
  count += 1
  for i in range(N):
    A[i] = A[i] / 2
from sys import stdin,stdout
from numba import njit
@njit
def fn(i):
    return pro[i]//(pro[i-k] if i-k>=0 else 1)
n,k=map(int,stdin.readline().split())
a=list(map(int,stdin.readline().split()))
pro=[a[0]]
for v in a[1:]:
    pro+=[pro[-1]*v]
for i in range(k,n):
    #print(fn(i),fn(i-1))
    if fn(i)>fn(i-1):print('Yes')
    else:print('No')


### FIXED CODE ###

from sys import stdin,stdout
n,k=map(int,stdin.readline().split())
a=list(map(int,stdin.readline().split()))
for i in range(k,n):
    print('Yes' if a[i]>a[i-k] else 'No')
s=input()+['']
n=0
for i in range(4):
    if s[i]==s[i+1]:
        n+=1
    else:
        n+=0
if n>0
    print('Bad')
else:
    print('Good')

### FIXED CODE ###

s=input()
n=0
for i in range(3):
    if s[i]==s[i+1]:
        n+=1
    else:
        n+=0
if n>=1:
    print('Bad')
else:
    print('Good')