Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())

def expectation(pp):
    return 1 + (0.5 * (pp - 1))

p = list(map(int, input().split()))
ep = tuple(map(expectation, p))

# print(ep)

# print(ep[0:K])

tmp_sum = sum(ep[0:K])
save_sum = tmp_sum

for i in range(1, N - K + 1):
    tmp = ep[i : i + K]
    tmp_sum -= ep[i - 1]
    tmp_sum += tmp[K - 1]
    save_sum = max(tmp_sum, save_sum)
    
print(save_sum)


Fixed submission:
N, K = map(int, input().split())

def expectation(pp):
    return 1 + (0.5 * (pp - 1))

p = list(map(int, input().split()))
ep = tuple(map(expectation, p))

cum = [0]
cum_append = cum.append
for i in range(N):
    cum_append(cum[i] + ep[i])

result = 0

for i in range(0, N - K + 1):
    tmp = cum[i + K] - cum[i]
    result = max(result, tmp)
    
print(result)

Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())

def expectation(pp):
    return (pp * (pp + 1) / 2) / pp

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

result = 0

save_max = 0
save_idx = 0

for i in range(N - K + 1):
    s = sum(p[i : i + K])
    if s > save_max:
        save_idx = i
        save_max = s
    
print(sum([expectation(pp) for pp in p[save_idx : save_idx + K]]))

Fixed submission:
N, K = map(int, input().split())

def expectation(pp):
    return 1 + (0.5 * (pp - 1))

p = list(map(int, input().split()))
ep = tuple(map(expectation, p))

cum = [0]
cum_append = cum.append
for i in range(N):
    cum_append(cum[i] + ep[i])

result = 0

for i in range(0, N - K + 1):
    tmp = cum[i + K] - cum[i]
    result = max(result, tmp)
    
print(result)

Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())

def expectation(pp):
    return (pp * (pp + 1) / 2) / pp

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

result = 0

ep = [expectation(pp) for pp in p]

save_max = 0

for i in range(N - K + 1):
    save_max = max(sum(ep[i : i + K]), save_max)
    
print(save_max)

Fixed submission:
N, K = map(int, input().split())

def expectation(pp):
    return 1 + (0.5 * (pp - 1))

p = list(map(int, input().split()))
ep = tuple(map(expectation, p))

cum = [0]
cum_append = cum.append
for i in range(N):
    cum_append(cum[i] + ep[i])

result = 0

for i in range(0, N - K + 1):
    tmp = cum[i + K] - cum[i]
    result = max(result, tmp)
    
print(result)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())

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

cnt = 0

for i in range(N):
    if i == 0:
        cnt += 1
    else:
        if all(list(map(lambda x:x > P[i], P[:i]))):
            cnt += 1

print(cnt)

Fixed submission:
N = int(input())

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

m = 2 * (10 ** 5) + 1

cnt = 0

for i in range(N):
    if P[i] < m:
        cnt += 1
        m = min(P[i], m)
    
print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
# author:  Taichicchi
# created: 17.09.2020 23:46:19


N = int(input())

S = input()

cnt = 0

for i in map(lambda x: str(x).zfill(3), range(1000)):
    f = 0
    for s in S:
        if s == i[f]:
            f += 1
        if f == 3:
            break
    if f == 3:
        cnt += 1

print(cnt)


Fixed submission:
# author:  Taichicchi
# created: 17.09.2020 23:46:19


N = int(input())

S = input()

cnt = 0

for i in map(lambda x: str(x).zfill(3), range(1000)):
    f = 0
    for s in S:
        if s == i[f]:
            f += 1
        if f == 3:
            break
    if f == 3:
        cnt += 1

print(cnt)

Buggy python submission (verdict: Time Limit Exceeded):
# author:  Taichicchi
# created: 17.09.2020 23:46:19

import sys

N = int(input())

S = input()

cnt = 0

for i in map(lambda x: str(x).zfill(3), range(1000)):
    f = 0
    for j in range(len(S)):
        if S[j] == i[f]:
            f += 1
        if f == 3:
            break
    if f == 3:
        cnt += 1

print(cnt)


Fixed submission:
# author:  Taichicchi
# created: 17.09.2020 23:46:19


N = int(input())

S = input()

cnt = 0

for i in map(lambda x: str(x).zfill(3), range(1000)):
    f = 0
    for s in S:
        if s == i[f]:
            f += 1
        if f == 3:
            break
    if f == 3:
        cnt += 1

print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
print(sum([i for i in range(N)]))

Fixed submission:
N = int(input())

if N % 2 == 0:
  print(int((N // 2) * (N - 1)))
else:
  print(int(N * ((N - 1) // 2)))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())

s = []
s_ap = s.append

for i in range(N):
    s_ap("".join(sorted(input())))

s.sort()

s_set = set(s)

result = 0

for _ in s_set:
    cnt = s.count(_)
    result += int(cnt * (cnt - 1) / 2)

print(result)

Fixed submission:
from collections import Counter

N = int(input())

s = []
s_ap = s.append

for i in range(N):
    s_ap("".join(sorted(input())))

result = 0

for i in Counter(s).values():
    if not i == 1:
        result += int(i * (i - 1) / 2)
        
print(result)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())

saved = []
cnt_ls = []
saved_ap = saved.append
cnt_ap = cnt_ls.append

for i in range(N):
    s = "".join(sorted(input()))
    if s not in saved:
        saved_ap(s)
        cnt_ap(1)
    else:
        cnt_ls[saved.index(s)] += 1

result = 0

for i in range(len(cnt_ls)):
    tmp = cnt_ls[i]
    result += int( tmp * (tmp - 1) / 2 )

print(result)



Fixed submission:
from collections import Counter

N = int(input())

s = []
s_ap = s.append

for i in range(N):
    s_ap("".join(sorted(input())))

result = 0

for i in Counter(s).values():
    if not i == 1:
        result += int(i * (i - 1) / 2)
        
print(result)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
s = []
for i in range(N):
    s.append("".join(sorted(input())))

result = 0

s_set = set(s)

for elem in s_set:
    cnt = s.count(elem)
    if cnt == 1:
        continue
    else:
        result += int(cnt * (cnt - 1) / 2)

print(result)

Fixed submission:
from collections import Counter

N = int(input())

s = []
s_ap = s.append

for i in range(N):
    s_ap("".join(sorted(input())))

result = 0

for i in Counter(s).values():
    if not i == 1:
        result += int(i * (i - 1) / 2)
        
print(result)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
s = []
for i in range(N):
    s.append("".join(sorted(input())))

result = 0

for i in range(N):
    for j in range(i + 1, N):
        if s[i] == s[j]:
            result += 1

print(result)

Fixed submission:
from collections import Counter

N = int(input())

s = []
s_ap = s.append

for i in range(N):
    s_ap("".join(sorted(input())))

result = 0

for i in Counter(s).values():
    if not i == 1:
        result += int(i * (i - 1) / 2)
        
print(result)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = []
A_ap = A.append
for i in range(N):
    A_ap(int(input()))
    
max_A = max(A)
for i in range(N):
    if A[i] != max_A:
        print(max_A)
    else:
        print(sorted(A)[-2])

Fixed submission:
N = int(input())
A = []
A_ap = A.append
for i in range(N):
    A_ap(int(input()))
    
max_A = sorted(A)[-1]
max_2A = sorted(A)[-2]
for i in range(N):
    if A[i] != max_A:
        print(max_A)
    else:
        print(max_2A)
Buggy python submission (verdict: Runtime Error):
import fractions

A, B, C, D = map(int, input().split())

s = B - A + 1

if A % C == 0 or A % D == 0:
    A -= 1

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

E = lcm(C, D)

val1 = A // C
val2 = B // C
val3 = A // D
val4 = B // D
val5 = A // E
val6 = B // E

print(s - (val2 - val1 + val4 - val3 - (val6 - val5)))


Fixed submission:
result = "Good"
s = list(input())
if s[0] == s[1] or s[1] == s[2] or s[2] == s[3]:
    result = "Bad"
print(result)

Buggy python submission (verdict: Runtime Error):
import math

A, B, C, D = map(int, input().split())

s = B - A + 1

if A % C == 0 or A % D == 0:
    A -= 1

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

E = lcm(C, D)

val1 = A // C
val2 = B // C
val3 = A // D
val4 = B // D
val5 = A // E
val6 = B // E

print(s - (val2 - val1 + val4 - val3 - (val6 - val5)))


Fixed submission:
result = "Good"
s = list(input())
if s[0] == s[1] or s[1] == s[2] or s[2] == s[3]:
    result = "Bad"
print(result)
Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
a = list(map(int, input().split()))

cnt = 0
def main():
  for i in range(N):
      for j in range(i + 1, N + 1):
          s = sum(a[i:j])
          if s >= K:
              cnt += N - ( j - 1 )
              break
  print(cnt)

if __name__ == "__main__":
  main()

Fixed submission:
X, A = map(int, input().split())
if X < A:
    print(0)
else:
    print(10)
Buggy python submission (verdict: Runtime Error):
N, A, B, C, D = map(int, input().split())

S = list(input().split()[0])

result = "Yes"

if C < D:
    for i in range(B, D - 1):
        if S[i] == "#" and S[i + 1] == "#":
                result = "No"
                print(result)
                break
else:
    for i in range(B, C - 1):
        if S[i] == "#" and S[i + 1] == "#":
                result = "No"
                print(result)
                flag = True
                break
    if not flag:
        for i in range(B - 1, C - 2):
            if S[i] == "." and S[i + 1] == "." and S[i + 2] == ".":
                print("Yes")
                break
        


Fixed submission:
N, A, B, C, D = map(int, input().split())

S = list(input().split()[0])

result = "Yes"
flag = False

for i in range(B, D - 1):
    if S[i] == "#" and S[i + 1] == "#":
        result = "No"
        print(result)
        flag = True
        break
if not flag:
    for i in range(A, C - 1):
        if S[i] == "#" and S[i + 1] == "#":
            result = "No"
            print(result)
            flag = True
            break

if not flag:    
    if A < B and B < D and D < C:
        for i in range(B - 2, D - 1):
            if S[i] == "." and S[i + 1] == "." and S[i + 2] == ".":
                result = "Yes"
                print(result)
                flag = True
                break
            else:
                result = "No"
                flag = False
if not flag:
    print(result)
Buggy python submission (verdict: Runtime Error):
A, B = list(map(int,input()))
def button(A, B):
  if A > B:
    result = A
    return([A - 1, B, result])
  elif A == B:
    result = A
    return([A - 1, B, result])
  else:
    result = B
    return([A, B - 1, result])
 
A, B, result_1 = button(A, B)
A, B, result_2 = button(A, B)
 
print(result_1 + result_2)

Fixed submission:
A, B = list(map(int,input().split()))
def button(A, B):
  if A > B:
    result = A
    return([A - 1, B, result])
  elif A == B:
    result = A
    return([A - 1, B, result])
  else:
    result = B
    return([A, B - 1, result])
 
A, B, result_1 = button(A, B)
A, B, result_2 = button(A, B)
 
print(result_1 + result_2)

Buggy python submission (verdict: Runtime Error):
A, B = list(map(int,input()))
def button(A, B):
  if A > B:
    result = A
    return([A - 1, B, result])
  elif A = B:
    result = A
    return([A - 1, B, result])
  else:
    result = B
    return([A, B - 1, result])

A, B, result_1 = button(A, B)
A, B, result_2 = button(A, B)

print(result_1 + result_2)

Fixed submission:
A, B = list(map(int,input().split()))
def button(A, B):
  if A > B:
    result = A
    return([A - 1, B, result])
  elif A == B:
    result = A
    return([A - 1, B, result])
  else:
    result = B
    return([A, B - 1, result])
 
A, B, result_1 = button(A, B)
A, B, result_2 = button(A, B)
 
print(result_1 + result_2)
Buggy python submission (verdict: Runtime Error):
ts = []
ts_mod = []
for i in range(5):
    ts.append(int(input()))
    ts_mod.append(ts[i] % 10)


def find_index(ts, ts_mod):
    result = 10
    for i in range(len(ts_mod)):
        if ts_mod[i] == 0:
            pass
        else:
            if result > ts_mod[i]:
                result = ts_mod[i]
    return ts_mod.index(result)

min_ind = find_index(ts, ts_mod)

last_ts = ts[min_ind]

del ts_mod[min_ind]
del ts[min_ind]


result = 0
for i in range(len(ts_mod)):
    if ts[i] % 10 == 0:
        result += ts[i]
    else:
        result += ts[i] + ( 10 - ts[i] % 10 )
        
result += last_ts
print(result)

Fixed submission:
ts = []
ts_mod = []
for i in range(5):
    ts.append(int(input()))
    ts_mod.append(ts[i] % 10)


def find_index(ts, ts_mod):
    if all([x == 0 for x in ts_mod]):
        return 0
    else:
        result = 10
        for i in range(len(ts_mod)):
            if ts_mod[i] == 0:
                pass
            else:
                if result > ts_mod[i]:
                    result = ts_mod[i]
        return ts_mod.index(result)

min_ind = find_index(ts, ts_mod)

last_ts = ts[min_ind]

del ts_mod[min_ind]
del ts[min_ind]


result = 0
for i in range(len(ts_mod)):
    if ts[i] % 10 == 0:
        result += ts[i]
    else:
        result += ts[i] + ( 10 - ts[i] % 10 )
        
result += last_ts
print(result)
Buggy python submission (verdict: Time Limit Exceeded):
# author:  Taichicchi
# created: 12.09.2020 19:26:19

import sys

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

S = input()

cum_ls = []


def cnt_ac(s):
    cnt = 0
    for i in range(N - 1):
        if s[i:i + 2] == "AC":
            cnt += 1
    return cnt


for i in range(N):
    cum_ls.append(cnt_ac(S[:i + 1]))

for i in range(Q):
    l, r = map(int, input().split())
    print(cum_ls[r - 1] - cum_ls[l - 1])


Fixed submission:
# author:  Taichicchi
# created: 12.09.2020 19:26:19

import sys

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

S = input()

cum_ls = [0]

for i in range(1, N):
    if S[i - 1: i + 1] == "AC":
        cum_ls.append(cum_ls[i - 1] + 1)
    else:
        cum_ls.append(cum_ls[i - 1])

# print(cum_ls)

for i in range(Q):
    l, r = map(int, input().split())
    print(cum_ls[r - 1] - cum_ls[l - 1])
Buggy python submission (verdict: Runtime Error):
A, B = list(map(int, input()))

if B % A == 0:
    print(A + B)
else:
    print(B - A)


Fixed submission:
A, B = list(map(int,input().split()))
if B % A == 0:
  print( A + B )
else:
  print( B - A )
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int,input().split()))

from functools import reduce
import math

R = reduce(math.gcd,A)

print(int(R))

Fixed submission:
# author:  Taichicchi
# created: 14.09.2020 22:18:44

import sys
from math import gcd

N = int(input())

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

ans = gcd(A[0], A[1])
for i in range(2, N):
    ans = gcd(ans, A[i])

print(ans)

Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int,input().split()))

from functools import reduce
import math

R = reduce(math.gcd,A)

print(R)

Fixed submission:
# author:  Taichicchi
# created: 14.09.2020 22:18:44

import sys
from math import gcd

N = int(input())

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

ans = gcd(A[0], A[1])
for i in range(2, N):
    ans = gcd(ans, A[i])

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# author:  Taichicchi
# created: 27.09.2020 23:15:22

import sys

N = int(input())

s = [int(input()) for _ in range(N)]

ans = 0

for i in range(2 ** N):
    score = 0
    for j in range(N):
        if (i >> j) & 1:
            score += s[j]

    if score % 10 == 0:
        score = 0

    ans = max(ans, score)


print(ans)


Fixed submission:
# author:  Taichicchi
# created: 27.09.2020 23:15:22

import sys

N = int(input())

s = [int(input()) for _ in range(N)]

ls = []

for i in range(N):
    if s[i] % 10 != 0:
        ls.append(s[i])

ls.sort()

base = sum(s)

if base % 10 != 0:
    print(base)
    exit()

if ls:
    print(base - ls[0])
else:
    print(0)
Buggy python submission (verdict: Runtime Error):
def dfs(v):
    global visited
    visited[v] = True
    for nv in graph[v]:
        if nv in graph[v]:
            if not visited[nv]:
                dfs(nv)


if __name__ == "__main__":
    N, M = map(int, input().split())
    graph = [[] for _ in range(N)]
    visited = [False]*N
    for _ in range(M):
        A, B = map(lambda x: int(x)-1, input().split())
        graph[A].append(B)
        graph[B].append(A)
    ans = -1
    for v in range(N):
        if not visited[v]:
            dfs(v)
            ans += 1
    print(ans)


Fixed submission:
import sys


def dfs(v):
    global visited
    visited[v] = True
    for nv in graph[v]:
        if nv in graph[v]:
            if not visited[nv]:
                dfs(nv)


if __name__ == "__main__":
    sys.setrecursionlimit(10**6)
    N, M = map(int, input().split())
    graph = [[] for _ in range(N)]
    visited = [False]*N
    for _ in range(M):
        A, B = map(lambda x: int(x)-1, input().split())
        graph[A].append(B)
        graph[B].append(A)
    ans = -1
    for v in range(N):
        if not visited[v]:
            dfs(v)
            ans += 1
    print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    K = int(input())
    first = 7 % K
    curr = first
    yet = True
    ans = 1
    while yet:
        if curr == 0:
            print(ans)
            return
        curr = (curr*10+7) % K
        if first == curr:
            yet = False
        ans += 1
    print(-1)


if __name__ == "__main__":
    main()


Fixed submission:
def main():
    K = int(input())
    curr = 7 % K
    for i in range(1, K+1):
        if curr == 0:
            print(i)
            return
        curr = (curr*10+7) % K
    else:
        print(-1)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    K = int(input())
    first = 7 % K
    curr = first
    yet = True
    ans = 1
    while yet:
        if curr == 0:
            print(ans)
            return
        curr = (curr*10+7) % K
        if first == curr:
            yet = False
        ans += 1
    print(-1)


if __name__ == "__main__":
    main()


Fixed submission:
def main():
    K = int(input())
    curr = 7 % K
    for i in range(1, K+1):
        if curr == 0:
            print(i)
            return
        curr = (curr*10+7) % K
    else:
        print(-1)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    K = int(input())
    first = 7 % K
    curr = first
    S = set()
    ans = 1
    while first not in S:
        if curr == 0:
            print(ans)
            return
        curr = (curr*10+7) % K
        S.add(curr)
        ans += 1
    print(-1)


if __name__ == "__main__":
    main()


Fixed submission:
def main():
    K = int(input())
    curr = 7 % K
    for i in range(1, K+1):
        if curr == 0:
            print(i)
            return
        curr = (curr*10+7) % K
    else:
        print(-1)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N, K = map(int, input().split())
    A = [1] + list(map(int, input().split()))
    for i in range(2, N+1):
        A[i] *= A[i-1]
    for i in range(K+1, N+1):
        cur = A[i]//A[i-K]
        prev = A[i-1]//A[i-K-1]
        if cur > prev:
            print("Yes")
        else:
            print("No")


if __name__ == "__main__":
    main()


Fixed submission:
def main():
    N, K = map(int, input().split())
    A = [1] + list(map(int, input().split()))
    for i in range(K+1, N+1):
        if A[i] > A[i-K]:
            print("Yes")
        else:
            print("No")


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def f(n):
    ans = 0
    for x in range(1, n):
        x2 = x**2
        if x2 > n-2:
            break
        for y in range(1, n):
            y2 = y**2
            if x2 + y2 + x*y > n-1:
                break
            for z in range(1, n):
                judge = x2 + y2 + z**2 + x*y + y*z + z*x
                if judge == n:
                    ans += 1
                elif judge > n:
                    break
    return ans


def main():
    N = int(input())
    for i in range(1, N+1):
        print(f(i))


if __name__ == "__main__":
    main()


Fixed submission:
def main():
    N = int(input())
    ans = [0]*(N+1)
    for x in range(1, 101):
        for y in range(1, 101):
            for z in range(1, 101):
                a = x*x + y*y + z*z + x*y + y*z + z*x
                if a <= N:
                    ans[a] += 1
    for i in range(1, N+1):
        print(ans[i])


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    ans = 1
    for a in A:
        ans *= a
    if ans > L:
        print(-1)
    else:
        print(ans)


if __name__ == "__main__":
    N = int(input())
    A = [int(a) for a in input().split()]
    L = 10**18
    main()


Fixed submission:
def main():
    if A.count(0) >= 1:
        print(0)
        return
    ans = 1
    for a in A:
        ans *= a
        if ans > L:
            print(-1)
            return
    print(ans)


if __name__ == "__main__":
    N = int(input())
    A = [int(a) for a in input().split()]
    L = 10**18
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    ans = 1
    for a in A:
        ans *= a
    if ans <= 10**18:
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    N = int(input())
    A = [int(a) for a in input().split()]
    main()


Fixed submission:
def main():
    if A.count(0) >= 1:
        print(0)
        return
    ans = 1
    for a in A:
        ans *= a
        if ans > L:
            print(-1)
            return
    print(ans)


if __name__ == "__main__":
    N = int(input())
    A = [int(a) for a in input().split()]
    L = 10**18
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import deque


input = sys.stdin.readline


def torf():
    for i in range(2, N):
        n = B[i-2]
        count = 1
        while n != 1:
            n = B[n-2]
            count += 1
        if count != D[i-1]:
            return False
    return True


def main():
    while que:
        nn = que.popleft()
        for n in edges[nn-1]:
            if D[n-1] == INF or D[n-1] > D[nn-1] + 1:
                D[n-1] = D[nn-1] + 1
                que.append(n)
                if n > 1:
                    B[n-2] = nn
    if torf():
        print("Yes")
        for b in B:
            print(b)
    else:
        print("No")


if __name__ == "__main__":
    N, M = map(int, input().split())
    edges = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        edges[a-1].append(b)
        edges[b-1].append(a)
    B = [0]*(N-1)
    que = deque([1])
    INF = 10**10
    D = [INF]*N
    D[0] = 0
    main()


Fixed submission:
import sys
from collections import deque


input = sys.stdin.readline


def main():
    while que:
        nn = que.popleft()
        for n in edges[nn-1]:
            if D[n-1] == INF or D[n-1] > D[nn-1] + 1:
                D[n-1] = D[nn-1] + 1
                que.append(n)
                if n > 1:
                    B[n-2] = nn
    print("Yes")
    for b in B:
        print(b)


if __name__ == "__main__":
    N, M = map(int, input().split())
    edges = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        edges[a-1].append(b)
        edges[b-1].append(a)
    B = [0]*(N-1)
    que = deque([1])
    INF = 10**10
    D = [INF]*N
    D[0] = 0
    main()