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

import queue
import sys
sys.setrecursionlimit(10**6)

N = int(input())
uvw = []
for _ in range(N-1):
    uvw.append(tuple(map(int, input().split())))

G=[[0]*(N+1) for _ in range(N+1)]
for el in uvw:
    G[el[0]][el[1]]=el[2]
    G[el[1]][el[0]] = el[2]
#print(G)

H=[[] for _ in range(N+1)]
for el in uvw:
    H[el[0]].append(el[1])
    H[el[1]].append(el[0])
#print(H)

seen=[False]*(N+1)
distance=[0]*(N+1)
todo=queue.Queue()
def dfs(n):
    seen[n]=True
    for nxt in H[n]:
        if seen[nxt] == False:
            distance[nxt] = distance[n] + G[n][nxt]
            todo.put(nxt)
    if todo.empty():
        return None
    else:
        dfs(todo.get())

dfs(1)
#print(distance)
#print(seen)

for val in distance[1:]:
    if val % 2 == 0:
        print(0)
    else:
        print(1)




### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

N = int(input())
uvw = []
for _ in range(N-1):
    uvw.append(tuple(map(int, input().split())))


H=[[] for _ in range(N+1)]
for el in uvw:
    H[el[0]].append((el[1], el[2]))
    H[el[1]].append((el[0], el[2]))
#print(H)

seen=[False]*(N+1)
color=[0]*(N+1)
def dfs(n):
    seen[n]=True
    for nxt in H[n]:
        if seen[nxt[0]] == False:
            if nxt[1] % 2 == 0:
                color[nxt[0]]=color[n]
            else:
                color[nxt[0]]=color[n] ^ 1
            dfs(nxt[0])

dfs(1)
#print(distance)
#print(seen)

for i in range(1,N+1):
    print(color[i])
### BUGGY CODE ###

N = 1000001
a = [0]* N
input()
b = sorted(map(int,input().split()))
for x in b:
  a[int(x)] += 1
for i in b:
  if a[i]:
    for j in range(i + i, N, i):
      a[j] = 0
print(a.count(1))


### FIXED CODE ###

N = 1000001
a = [0]* N
input()
for x in input().split():
  a[int(x)] += 1
for i in range(1, N):
  for j in range(i + i, N, i):
    if a[i]:
      a[j] = 0
print(a.count(1))
### BUGGY CODE ###

N, W = map(int, input().split())
w = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())
dp = [[0] * (W + 1) for _ in range(N + 1)]
for i in range(N):
    for j in range(W + 1):
        if j - w[i] >= 0:
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - w[i]] + v[i])
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
print(dp[N][W])

### FIXED CODE ###

N, W = map(int, input().split())
w = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())
dp = [[0] * (W + 1) for _ in range(N + 1)]
for i in range(N):
    for j in range(W + 1):
        if j - w[i] >= 0:
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - w[i]] + v[i])
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
print(dp[N][W])
### BUGGY CODE ###

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

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    x = I()

    c = collections.defaultdict(int)
    r = 1
    c[0] = 1
    z = 1
    t = 0
    while True:
        r += 1
        t += x
        t %= 360
        if t >= 180:
            c[t - 180] -= 1
        else:
            c[t] += 1

        if all(v == 0 for v in c.values()):
            return r

    return -1


print(main())




### FIXED CODE ###

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

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    x = I()

    g = math.gcd(x, 360)

    return 360 // g


print(main())
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10**9)
mod = 998244353

def main():
    N, S = map(int, input().split())
    A = list(map(int, input().split()))
    d = {}

    def g(n, S):
        if S < 0: return 0
        if S == 0: return pow(2, n + 1, mod) - 1
        if n == 0 and S == A[0]: return 1
        if n == 0: return 0
        if (n, S) in d: return d[(n, S)]
        val = (g(n - 1, S) * 2 + g(n - 1, S - A[n])) % mod
        if A[n] == S: val += 1
        d[(n, S)] = val % mod
        return d[(n, S)]
    
    print(g(N - 1, S))

    

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()
from functools import lru_cache
sys.setrecursionlimit(10**9)
mod = 998244353

def main():
    N, S = map(int, input().split())
    A = list(map(int, input().split()))

    """
    再帰の計算式自体は合っていた！
    メモ化再帰とdpで計算量は変わらないはずだが、取りあえずdpで書き直してみる。
    """

    dp = [[0] * (S + 1) for _ in range(N)] # dp[n][s] = (N=n, S=sに対する問題の解)
    dp[0][0] = 1
    for n in range(1, N): dp[n][0] = (dp[n - 1][0] * 2 + 1) % mod
    for s in range(1, S + 1): dp[0][s] = 1 if s == A[0] else 0
    for n in range(1, N):
        for s in range(1, S + 1):
            dp[n][s] = (dp[n - 1][s] * 2 + dp[n - 1][s - A[n]]) if s >= A[n] else dp[n - 1][s] * 2
            if A[n] == s: dp[n][s] += 1
            dp[n][s] %= mod
    print(dp[N - 1][S])

    

if __name__ == "__main__":
    main()
### BUGGY CODE ###

N = int(input())
pre_t = 0
pre_x = 0
pre_y = 0
count = 0
for _ in range(N):
    flag = False
    t, x, y = map(int, input().split())
    for a in range(t - pre_t + 1):
        for b in range(t- pre_t + 1 - a):
            for c in range(t - pre_t + 1  - a - b):
                d = t - pre_t - a - b - c
                if pre_x + a - b == x and pre_y + c - d == y:
                    count += 1
                    flag = True
                    break
            if flag:
                break
        if flag:
            break
    pre_t = t
    pre_x = x
    pre_y = y
if count == N:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

N = int(input())
pre_t = 0
pre_x = 0
pre_y = 0
count = 0
for _ in range(N):
    flag = False
    t, x, y = map(int, input().split())
    for a in range(t - pre_t + 1):
        b = pre_x - x + a
        if b >= 0:
            for c in range(t - pre_t + 1  - a - b):
                d = t - pre_t - a - b - c
                if pre_y + c - d == y:
                    count += 1
                    flag = True
                    break
        if flag:
            break
    pre_t = t
    pre_x = x
    pre_y = y
if count == N:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

n = int(input())
h = list(map(int, input().split()))
flag = 0
for i in range(n-1):  
  for j in range(i+1, n):
    if h[i] > h[j] + 1:
      flag = 1
      break

  if flag == 1:
    print("No")
    break

if flag == 0:
  print("Yes")

### FIXED CODE ###

n = int(input())
h = list(map(int, input().split()))
current_max = 0
for i in range(n):  
  if current_max > h[i] + 1:
    print("No")
    break
  else: 
    current_max = max(current_max, h[i])
    if i == n-1:
      print("Yes")
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)


def dp(i, j):
    if i == 0:
        if j:
            return -float('inf')
        else:
            return 0
    if j:
        return max(dp(i-1, False) - a[i-1], dp(i-1, True) + a[i-1])
    else:
        return max(dp(i-1, False) + a[i-1], dp(i-1, True) - a[i-1])


n = int(input())
a = list(map(int, input().split()))
print(dp(n, False))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
c = 0
z = False
for aa in a:
    if aa < 0:
        c += 1
    elif aa == 0:
        z = True
if z or c % 2 ==0:
    print(sum(map(abs, a)))
else:
    ab = [abs(x) for x in a]
    ans = sum(ab) - min(ab)*2
    print(ans)
### BUGGY CODE ###

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

query = [""]*q
f = [""]*q
c = [""]*q

for i in range(q):
    query[i] = input()
    if query[i]=="1":
        s = s[::-1]
    else:
        r = query[i].split()
        if r[1]=="1":
            s = r[2]+s
        elif r[1]=="2":
            s = s+r[2]

print(s)

### FIXED CODE ###

from collections import deque

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

query = []
rev=1

for i in range(q):
    query.append(input().split())

for i in range(q):
    if query[i][0]=="1":
        rev*=-1
    else:
        if rev==1:
            if query[i][1]=="1":
                s.appendleft(query[i][2])
            else:
                s.append(query[i][2])
        else:
            if query[i][1]=="2":
                s.appendleft(query[i][2])
            else:
                s.append(query[i][2])

result="".join(list(s))
if rev==-1:
    result = result[::-1]
print(result)
### BUGGY CODE ###

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

for i in range(N-1):
    for j in range(N-i-1):
        value += A[i]*A[i+j+1]  


ans = value % (1*10**9 + 7)

print(ans)


### FIXED CODE ###

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

A_sum = sum(A)

value = 0
ans = 0

for i in range(N-1):
    A_sum -= A[i]
    value += A[i]*A_sum

ans = value % (1*10**9+7)

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

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

  num_ones = [0 for x in range(60)]
  for i in range(N):
    k = A[i]
    cnt = 0
    while k:
      num_ones[cnt] += k % 2
      cnt += 1
      k //= 2

  powers_of_two = [1]
  for i in range(1,60):
    powers_of_two.append((powers_of_two[-1] * 2) % 1000000007)
  
  ans = 0
  for i in range(N-1):
    for j in range(60):
      if A[i] % 2 == 0:
        ans = (ans + powers_of_two[j] * num_ones[j]) % 1000000007
      else:
        num_ones[j] -= 1
        ans = (ans + powers_of_two[j] * (N - i - 1 - num_ones[j])) % 1000000007
      A[i] //= 2
  print(ans)
        
d()

### FIXED CODE ###

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

ans = 0
for i in range(60):
  p = 1 << i
  num_one = len([1 for x in A if x & p])
  ans = ans + p * num_one * (N - num_one)
print(ans % 1000000007)
### BUGGY CODE ###

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

C=''

for i in range(N):
    C+=str(A.index(i+1)+1)+' '
print(C[0:-1])

### FIXED CODE ###

N=int(input())
A=list(map(int, input().split()))
B=[0]*N
C=''
 
for i in range(N):
    B[A[i]-1]=i+1
 
for i in range(N):
    C+=str(B[i])+' '
 
print(C[0:-1])
### BUGGY CODE ###

def knapsack(C,n,wei,val,mat):
    if(C==0 or n==0):
        return 0
    else:
        if(C>=wei[n-1]):
            a=mat[C-wei[n-1]][n-1]
            b=mat[C][n-1]
            if(a==-1):
                a=knapsack(C-wei[n-1],n-1,wei,val,mat)
                mat[C-wei[n-1]][n-1]=a
            if(b==-1):
                b=knapsack(C,n-1,wei,val,mat)
                mat[C][n-1]=b
            mat[C][n]=max(a+val[n-1],b)
            return (max(a+val[n-1],b))
        else:
            alp=matrix[C][n-1]
            if(alp==-1):
                alp=knapsack(C,n-1,wei,val,mat)
                mat[C][n-1]=alp
                mat[C][n]=alp
            return (alp)
N,W=map(int,input().split())
matrix=[[-1 for i in range(0,N+1)]for j in range(0,W+1)]
for i in range(0,len(matrix)):
    matrix[i][0]=0
for i in range(0,len(matrix[0])):
    matrix[0][i]=0
weights=[]
values=[]
for i in range(0,N):
    w,v=map(int,input().split())
    weights.append(w)
    values.append(v)
knapsack(W,N,weights,values,matrix)
print(matrix[W][N])

### FIXED CODE ###

from sys import stdin,stdout
N,W=map(int,stdin.readline().split())
matrix=[[-1 for i in range(0,W+1)]for j in range(0,N+1)]
for i in range(0,len(matrix)):
    matrix[i][0]=0
for i in range(0,len(matrix[0])):
    matrix[0][i]=0
weights=[]
values=[]
for i in range(0,N):
    w,v=map(int,stdin.readline().split())
    weights.append(w)
    values.append(v)
for item in range(1,N+1):
    for weight in range(1,W+1):
        if(weights[item-1]<=weight):
            matrix[item][weight]=max(values[item-1]+matrix[item-1][weight-weights[item-1]],matrix[item-1][weight])
        else:
            matrix[item][weight]=matrix[item-1][weight]
print(matrix[N][W])
### BUGGY CODE ###

import math

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

ans = 0

for x in range(n + 1):
  new = math.floor((a * x) / b) - a * math.floor(x / b)
  if new > ans:
    ans = new

print(ans)


### FIXED CODE ###

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

if b <= n:
  if n != 1:
    n = b - 1

ans1 = math.floor((a * n) / b)
ans2 = a * math.floor(n / b)
ans3 = ans1 - ans2

print(ans3)
### BUGGY CODE ###

import bisect
n = int(input())
list_A = list(map(int, input().split()))
list_B = list(map(int, input().split()))
list_C = list(map(int, input().split()))
list_A.append(pow(10, 18))
list_B.append(pow(10, 18))
list_A.sort()
list_B.sort()
list_C.sort()
ans = 0

for i in range(n):
    c = list_C[i]
    j = bisect.bisect_left(list_B, c)
    for k in range(j):
        b = list_B[k]
        ans += bisect.bisect_left(list_A, b)

print(ans)

### FIXED CODE ###

n = int(input())
list_A = list(map(int, input().split()))
list_B = list(map(int, input().split()))
list_C = list(map(int, input().split()))
list_A.sort()
list_B.sort()
list_C.sort()
b = 0
list_UP = []
for i in range(n):
    while True:
        if b > n-1 or list_A[i] < list_B[b]:
            break
        b += 1
    list_UP.append(n-b)


c = 0
list_DOWN = []
for i in range(n):
    while True:
        if c > n-1 or list_B[i] < list_C[c]:
            break
        c += 1
    list_DOWN.append(n-c)


ans = 0
num = 0
sum_value = sum(list_DOWN)
for i in list_UP:
    while True:
        if num == n-i:
            break
        sum_value -= list_DOWN[num]
        num += 1
    ans += sum_value

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

N = int(input())
S = [input() for i in range(N)]
count = N
for i in range(N-1):
  for j in range(i+1, N):
    if S[i] == S[j]:
      count -= 1
      break
print(count)

### FIXED CODE ###

N = int(input())
list=[]
for _ in range(N):
  S = input()
  list.append(S)
print(len(set(list)))
### BUGGY CODE ###

class UnionFind(): # 0インデックス
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        '''
        xとyは-=1して使う
        '''
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

if __name__ == "__main__":
    N, M = map(int, input().split()) # N人、M個の関係
    union_find = UnionFind(N)
    for _ in range(M):
        A, B = map(int, input().split())
        A -= 1
        B -= 1
        union_find.union(A, B)

    group_dict = union_find.all_group_members()
    answer = 0
    for v in group_dict.values():
        answer = max(answer, len(v))
        
    print(answer)

### FIXED CODE ###

import math

class UnionFind(): # 0インデックス
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        '''
        xとyは-=1して使う
        '''
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

if __name__ == "__main__":
    N, M = map(int, input().split()) # N人、M個の関係
    union_find = UnionFind(N)
    for _ in range(M):
        A, B = map(int, input().split())
        A -= 1
        B -= 1
        union_find.union(A, B)

    answer = 0
    for i in range(N):
        answer = max(answer, union_find.size(i))

    print(answer)
### BUGGY CODE ###

N = int(input())
s = [0]*N
for i in range(N):
    s[i] = input()
ans = 0

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

print(ans)

### FIXED CODE ###

N = int(input())
s = [0]*N
p = {}
ans = 0
for i in range(N):
    s[i] = "".join(sorted(input()))
    if s[i] in p:
        ans += p[s[i]]
        p[s[i]] += 1
    else:
        p[s[i]] = 1

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

import bisect
N, K = [int(_) for _ in input().split()]
A = sorted([int(_) for _ in input().split()])


def solve(N, K, A):
    lb = -10**18 - 1
    rb = 10**18 + 1

    def check(x):
        #x以下の積がK個以上ある
        cnt = 0
        for i, a in enumerate(A):
            #区間i2∈[0,i) でA[i]*A[i2]<=xとなるようなi2の個数
            l = 0
            r = i
            if a > 0:
                l = -float('inf')
                r = bisect.bisect(A, x // a)
            elif a < 0:
                l = bisect.bisect_left(A, 0 - x // (-a))
                r = float('inf')
            elif x < 0:
                r = 0
            l = min(max(l, 0), i)
            r = max(min(r, i), 0)
            cnt += r - l
        return cnt >= K

    # Min x for check(x) == True
    while rb - lb > 1:
        mid = (rb + lb) // 2
        if check(mid):
            rb = mid
        else:
            lb = mid
    print(rb)


solve(N, K, A)


### FIXED CODE ###

import numpy as np
from numba import njit
N,K=[int(_) for _ in input().split()]
A = np.array([int(_) for _ in input().split()],dtype=int)
A.sort()


@njit
def main(N,K,A):
    lb = -10**18-1
    rb = 10 ** 18 + 1
    while rb - lb > 1:
        target = (rb + lb) // 2
        if 1:
            cnt=0
            for i, a in enumerate(A):
                if a==0:
                    d = i if target >= 0 else 0
                elif a < 0:
                    il = np.searchsorted(A,0- (-target)//a,side='left')
                    d = max(i - il, 0)
                else:
                    ir = np.searchsorted(A,target//a,side='right')
                    d = min(ir, i)
                cnt+=d
        if cnt>=K:
            rb = target
        else:
            lb = target
    return rb

print(main(N,K,A))
### BUGGY CODE ###

h,w=map(int,input().split())
maze=[["#" for i in range(2+w)]]
for _ in range(h):
    x=list(input())
    x.insert(0,"#")
    x.append("#")
    maze.append(x)
    
maze.append(["#" for i in range(2+w)])

#maze[i][j]=(i,j)番目の様子がどうなっているか。"#"の時地雷、"."の時oke

from collections import deque

d=deque()
d.append((1,1))





visited=[[False for i in range(w+2)] for j in range(h+2)]

dis=0
visited[1][1]=True

while visited[h][w]==False:
    e=deque()
    dis+=1
    while d:
    	x=d.popleft()
    	X,Y=x[0],x[1]
    	if visited[X-1][Y]==False and maze[X-1][Y]==".":
        	visited[X-1][Y]=True
        	e.append((X-1,Y))
    	if visited[X+1][Y]==False and maze[X+1][Y]==".":
        	visited[X+1][Y]=True
        	e.append((X+1,Y))
    	if visited[X][Y-1]==False and maze[X][Y-1]==".":
        	visited[X][Y-1]=True
        	e.append((X,Y-1))
    	if visited[X][Y+1]==False and maze[X][Y+1]==".":
        	visited[X][Y+1]=True
        	e.append((X,Y+1))
    if e:
      d=e
      e=deque()

    
dis=dis+1

cnt=0

#全体の白い領域を見る
for i in range(h+2):
    for j in range(2+w):
        if maze[i][j]==".":
            cnt+=1
        
        
print(cnt-dis)


### FIXED CODE ###

from collections import deque
d=deque()
e=deque()
h,w=map(int,input().split())
field=[0 for i in range(h+2)]
field[0]=[True for i in range(w+2)]
distance=0
white=0
for i in range(h):
    s=input()
    a=[False for i in range(w+2)]
    a[0]=True
    for j in range(w):
        if s[j]=="#":
            a[j+1]=True
        else:
            white+=1

    a[w+1]=True
    field[i+1]=a
field[h+1]=[True for i in range(w+2)]
d.append((1,1))
ans=-1
while d:
    while d:
        some=d.popleft()
        index1,index2=some[0],some[1]
        if index1==h and index2==w:
            ans=distance
        if field[index1-1][index2]==False:
                field[index1-1][index2]=True
                e.append((index1-1,index2))
        if field[index1+1][index2]==False:
                field[index1+1][index2]=True
                e.append((index1+1,index2))
        if field[index1][index2+1]==False:
                field[index1][index2+1]=True
                e.append((index1,index2+1))
        if  field[index1][index2-1]==False:
                field[index1][index2-1]=True
                e.append((index1,index2-1))
    distance+=1
    d=e
    e=deque()
if ans>=0:
    print(white-ans-1)
else:
    print(-1)
### BUGGY CODE ###

# https://atcoder.jp/contests/abc168/tasks/abc168_d
N, M = map(int, input().split(' '))

A = []
B = []
for i in range(M):
    _a, _b = map(int, input().split(' '))
    A.append(_a)
    B.append(_b)

# 道の接続マップ
route2 = {}

for a, b in zip(A, B):
    route2.update({(a - 1, b - 1): True})
    route2.update({(b - 1, a - 1): True})

# 探索する
room_depth = [None] * N
room_depth[0] = 0
room_sign = [None] * N

# 次に行く部屋
stack = [0]

while stack:
    now = stack.pop()
    for j in range(N):
        if (now, j) in route2.keys():
            if room_depth[j] is None or room_depth[j] > room_depth[now] + 1:
                room_depth[j] = room_depth[now] + 1
                room_sign[j] = now + 1
                stack.append(j)

print('Yes')
for s in room_sign[1:]:
    print(s)


### FIXED CODE ###

# https://atcoder.jp/contests/abc168/tasks/abc168_d
from collections import deque

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

A = []
B = []

# 隣接リスト
route2 = [[] for n in range(N)]

for i in range(M):
    a, b = map(int, input().split(' '))
    A.append(a)
    B.append(b)

for a, b in zip(A, B):
    route2[a - 1].append(b - 1)
    route2[b - 1].append(a - 1)

room_sign = [None] * N

queue = deque([])
visited = set()

queue.append(0)
visited.add(0)

while len(queue) > 0:
    now = queue.popleft()
    for i in route2[now]:
        if i not in visited:
            queue.append(i)
            visited.add(i)

            room_sign[i] = now + 1

print('Yes')
for s in room_sign[1:]:
    print(s)