Harryxun/stf_run huggingface dataset:
N = int(input())
dp = [[[[0 for l in range(4)] for k in range(4)]
       for j in range(4)] for i in range(N)]
for j in range(4):
    for k in range(4):
        for l in range(4):
            if not (j == 0 and k == 1 and l == 2)\
                    and not(j == 0 and k == 2 and l == 1)\
                    and not (j == 2 and k == 0 and l == 1):
                dp[2][j][k][l] = 1
for i in range(2, N-1):
    for j in range(4):
        for k in range(4):
            for l in range(4):
                dp[i][j][k][l] %= 10**9+7
                dp[i+1][k][l][0] += dp[i][j][k][l]
                # 0123: ACGT
                # AG?
                # ?GA
                # A?G
                # ?AG
                if not (j == 0 and k == 2) \
                   and not (k == 2 and l3 == 0)\
                   and not (j == 0 and l == 2)\
                   and not (k == 0 and l == 2):
                    dp[i+1][k][l][1] += dp[i][j][k][l]
                # ?AC
                if not (k == 0 and l == 1):
                    dp[i+1][k][l][2] += dp[i][j][k][l]
                dp[i+1][k][l][3] += dp[i][j][k][l]
ans = 0
for j in range(4):
    for k in range(4):
        for l in range(4):
            ans += dp[N-1][j][k][l]
ans %= 10**9+7
print(ans)


### FIXED CODE ###

N = int(input())
dp = [[[[0 for l in range(4)] for k in range(4)]
       for j in range(4)] for i in range(N)]
for j in range(4):
    for k in range(4):
        for l in range(4):
            if not (j == 0 and k == 1 and l == 2)\
                    and not(j == 0 and k == 2 and l == 1)\
                    and not (j == 2 and k == 0 and l == 1):
                dp[2][j][k][l] = 1
for i in range(2, N-1):
    for j in range(4):
        for k in range(4):
            for l in range(4):
                dp[i][j][k][l] %= 10**9+7
                dp[i+1][k][l][0] += dp[i][j][k][l]
                # 0123: ACGT
                # AG?
                # ?GA
                # A?G
                # ?AG
                if not (j == 0 and k == 2) \
                   and not (k == 2 and l == 0)\
                   and not (j == 0 and l == 2)\
                   and not (k == 0 and l == 2):
                    dp[i+1][k][l][1] += dp[i][j][k][l]
                # ?AC
                if not (k == 0 and l == 1):
                    dp[i+1][k][l][2] += dp[i][j][k][l]
                dp[i+1][k][l][3] += dp[i][j][k][l]
ans = 0
for j in range(4):
    for k in range(4):
        for l in range(4):
            ans += dp[N-1][j][k][l]
ans %= 10**9+7
print(ans)
a,b,k=map(int,input().split())
if a>=k:
  print(a-k,b)
elif:
  print(0,max(b+a-k,0))

### FIXED CODE ###

a,b,k=map(int,input().split())
if a>=k:
  print(a-k,b)
else:
  print(0,max(b+a-k,0))
import sys


def solve(n, m, links, parents):
    if m % 2 == 1:
        print(-1)
        return

    fixed = [len(l) % 2 == 0 for l in links]

    def reverse_links(s, t):
        v = s
        while v != t:
            p = parents[v]
            links[p][v] ^= 1
            v = p

    # print(links)
    # print(parents)
    # print(fixed)

    tmp_vertices = set()
    tmp_pair = -1
    for v in range(n - 1, -1, -1):
        if fixed[v]:
            continue
        exist_pair = tmp_pair != -1
        p = parents[v]
        if not exist_pair:
            tmp_vertices.add(v)
            while p != -1:
                tmp_vertices.add(p)
                p = parents[p]
        elif v == 0:
            reverse_links(tmp_pair, v)
        else:
            # print(v, u, p, exist_pair, tmp_vertices, tmp_pair)
            while p != -1:
                if p in tmp_vertices:
                    reverse_links(v, p)
                    reverse_links(tmp_pair, p)
                    break
                p = parents[p]
        if exist_pair:
            tmp_vertices.clear()
            tmp_pair = -1
        else:
            tmp_pair = v

    ans = []
    for v in range(n):
        for u, d in links[v].items():
            if d == 0:
                ans.append('{} {}'.format(v + 1, u + 1))
            else:
                ans.append('{} {}'.format(u + 1, v + 1))
    print('\n'.join(ans))


n, m = list(map(int, input().split()))
links = [{} for _ in range(n)]
parents = [-1] * n
for line in sys.stdin:
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    if a > b:
        a, b = b, a
    links[a][b] = 0
    parents[b] = a
solve(n, m, links, parents)


### FIXED CODE ###

import sys
from collections import deque

sys.setrecursionlimit(10 ** 5)


def solve(n, m, links):
    if m % 2 == 1:
        print(-1)
        return

    tree = [set() for _ in range(n)]
    parents = [-1] * n
    q = deque([0])
    while q:
        v = q.popleft()
        for u in links[v]:
            if parents[u] == -1:
                tree[v].add(u)
                parents[u] = v
                q.append(u)
            links[u].remove(v)

    parities = [len(l) % 2 for l in links]

    # print(links)
    # print(tree)
    # print(parents)
    # print(parities)

    def dfs(v):
        b = parities[v]
        for u in tree[v]:
            c = dfs(u)
            b ^= c
        if b:
            p = parents[v]
            links[p].remove(v)
            links[v].add(p)
        return b

    dfs(0)

    ans = ['{} {}'.format(v + 1, u + 1) for v in range(n) for u in links[v]]
    print('\n'.join(ans))


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

links = [set() for _ in range(n)]
for line in sys.stdin:
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)

solve(n, m, links)
N = int(input())
S = input()
cnt = 0
if S[0] == '#' and S[1] == '.':
    S.replace(S[0], '.')
    cnt += 1

i = 1
for i in range(N - 2):
    if S[i] == '#' and S[i + 1] == '.':
        if S[i - 1] == '.':
            S.replace(S[i], '.')
        else:
            S.replace(S[i + 1], '#')        
        cnt += 1
print(cnt)

### FIXED CODE ###

N = int(input())
S = input()
i = 0
b = S.count('.')
w = 0
min = b
for i in range(N):
    if S[i] == '#':
        w += 1
    else:
        b -= 1
    
    T = b + w
    if T < min:
        min = T

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

a = [(i, ai) for i, ai in enumerate(A)]
a = sorted(key=lambda x: x[1], reverse=True)

# import numpy as np
# dp = np.zeros((N+1, N+1), np.int8)

dp = [[0] * (N + 1) for _ in range(N + 1)]

dp[0][0] = 0
for i, ai in enumerate(a):
    for l in range(i+1):
        r = i - l
        dp[i+1][l] = max(dp[i+1][l], dp[i][l] + ai[1] * ((N-1-r) - ai[0]))
        dp[i+1][l+1] = max(dp[i+1][l+1], dp[i][l] + ai[1] * (ai[0] - l))

print(max(dp[N]))

### FIXED CODE ###

def solve(N, A):
    a = [(i, ai) for i, ai in enumerate(A)]
    a.sort(key=lambda x: x[1], reverse=True)

    # import numpy as np
    # dp = np.zeros((N+1, N+1), np.int8)

    dp = [[0] * (N + 1) for _ in range(N + 1)]

    dp[0][0] = 0
    for i, ai in enumerate(a):
        for l in range(i+1):
            r = i - l
            dp[i+1][l] = max(dp[i+1][l], dp[i][l] + ai[1] * ((N-1-r) - ai[0]))
            dp[i+1][l+1] = max(dp[i+1][l+1], dp[i][l] + ai[1] * (ai[0] - l))

    print(max(dp[N]))

N = int(input())
A = list(map(int, input().split()))
solve(N,A)
N,M = map(int,input().split())
A = list(map(int,input().split()))
weight = [0,2,5,5,4,5,6,3,7,6]
dp=[-1]*(N+1)
dp[0] = 0

for i in range(N+1):
  if dp[i] == -1: continue
  for a in A:
    if i+weight[a]<N+1:
      dp[i+weight[a]] = max(dp[i+weight[a]],dp[i]*10+a)
      print(dp)

print(dp[-1])

### FIXED CODE ###

N,M = map(int,input().split())
A = list(map(int,input().split()))
weight = [0,2,5,5,4,5,6,3,7,6]
dp=[-1]*(N+1)
dp[0] = 0

for i in range(N+1):
  if dp[i] == -1: continue
  for a in A:
    if i+weight[a]<N+1:
      dp[i+weight[a]] = max(dp[i+weight[a]],dp[i]*10+a)

print(dp[-1])
A, B, C, D = map(int,input().split())

while(A or C != 0):
    C = C - B
    if(C <= 0):
        print("Yes")
        break
    A = A - D
    if(A <= 0):
        print("No")
        break

### FIXED CODE ###

s, w = map(int,input().split())

if(s <= w):
    print("unsafe")
else:
    print("safe")
h, w = map(int, input().split())
T = [[] for i in range(h)]
S = [[0] * w for i in range(h)]
for i in range(h):
    a = list(map(int, input().split()))
    T[i] = a

for i in range(h):
    for j in range(w):
        T[i][j] = T[i][j] % 2

rec = []
for i in range(h):
    for j in range(w):
        if T[i][j] == 1:
            rec.append((i, j))

rec = sorted(rec)
rec = sorted(rec, key=lambda s: s[1])
move = []
for i in range(0, len(rec), 2):
    if i + 1 == len(rec):
        break
    a, b = rec[i], rec[i + 1]
    sx = a[0]
    sy = a[1]
    tx = b[0]
    ty = b[1]
    while sx != tx and S[sx][sy] != 1:
        move.append((sx, sy, sx + 1, sy))
        S[sx][sy] = 1
        sx += 1
    if sy <= ty:
        while sy != ty and S[sx][sy] != 1:
            move.append((sx, sy, tx, sy + 1))
            S[sx][sy] = 1
            sy += 1
    else:
        while sy != ty and S[sx][sy] != 1:
            move.append((sx, sy, tx, sy - 1))
            S[sx][sy] = 1
            sy -= 1

print(len(move))
for i in range(len(move)):
    x, y, w, z = move[i][0] + 1, move[i][1] + 1, move[i][2] + 1, move[i][3] + 1
    print(x, y, w, z)


### FIXED CODE ###

h, w = map(int, input().split())
T = [[] for i in range(h)]
S = [[0] * w for i in range(h)]
for i in range(h):
    a = list(map(int, input().split()))
    T[i] = a

for i in range(h):
    for j in range(w):
        T[i][j] = T[i][j] % 2

move = []
i = 0
j = 0
k = 0
flag = False
while True:
    px, py = i, j
    if T[i][j] == 1:
        flag = True
    if i % 2 == 0:
        j += 1
        if j == w:
            j -= 1
            i += 1
        if i == h:
            break
        if flag:
            move.append((px, py, i, j))
        if flag and T[i][j] == 1:
            T[i][j] = 0
            flag = False
        k += 1
    else:
        j -= 1
        if j == -1:
            j += 1
            i += 1
        if i == h:
            break
        if flag:
            move.append((px, py, i, j))
        if flag and T[i][j] == 1:
            T[i][j] = 0
            flag = False

print(len(move))
for i in range(len(move)):
    x, y, w, z = move[i][0] + 1, move[i][1] + 1, move[i][2] + 1, move[i][3] + 1
    print(x, y, w, z)
r = int(inpnut())
print(r*r)

### FIXED CODE ###

r = int(input())
print(r*r)
n,k=map(int,input().split())
mod=10**9+7
root=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    root[a-1].append(b-1)
    root[b-1].append(a-1)
def perm(k,n):
    x=1
    if k-n+1<=0:
        return 0
    for i in range(k,k-n,-1):
        x=x*i%mod
    return x
def dfs(node,depth,prev): 
    l=len(root[node])
    d=depth
    x=1
    if l==0:
        return 1
    if l==1 and depth>1:
        return 1
    if depth>1:
        x=perm(k-d,l-1)
    else:
        x=perm(k-d,l)
    for y in root[node]:
        if y!=prev:
            x=x*dfs(y,min(depth+1,2),node)%mod
    return x
count=dfs(0,1,0)*k%mod
print(count if count>0 else 0)

### FIXED CODE ###

n,k=map(int,input().split())
mod=10**9+7
import sys
sys.setrecursionlimit(10**9)
root=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    root[a-1].append(b-1)
    root[b-1].append(a-1)
def perm(k,n):
    x=1
    if k-n+1<=0:
        return 0
    for i in range(k,k-n,-1):
        x=x*i%mod
    return x
def dfs(node,depth,prev): 
    l=len(root[node])
    d=depth
    x=1
    if l==0:
        return 1
    if l==1 and depth>1:
        return 1
    if depth>1:
        x=perm(k-d,l-1)
    else:
        x=perm(k-d,l)
    for y in root[node]:
        if y!=prev:
            x=x*dfs(y,2,node)%mod
    return x%mod
count=dfs(0,1,0)*k%mod
print(count if count>0 else 0)
from a import resolve

import sys
from io import StringIO
import unittest

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """2 2
2 0
0 0
-1 0
1 0"""
        output = """2
1"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """3 4
10 10
-10 -10
3 3
1 2
2 3
3 5
3 5"""
        output = """3
1
2"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """5 5
-100000000 -100000000
-100000000 100000000
100000000 -100000000
100000000 100000000
0 0
0 0
100000000 100000000
100000000 -100000000
-100000000 100000000
-100000000 -100000000"""
        output = """5
4
3
2
1"""
        self.assertIO(input, output)

if __name__ == "__main__":
    unittest.main()


### FIXED CODE ###

import math

INF = 1001001001

def resolve():
  n, m = map(int, input().split())
  s = []
  c = []

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

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

  for a in s:
    ans = 0
    dist = INF
    for i in range(m):
      if abs(a[0] - c[i][0]) + abs(a[1] - c[i][1]) < dist:
        dist = abs(a[0] - c[i][0]) + abs(a[1] - c[i][1])
        ans = i+1
    print(ans)
  return

if __name__ == "__main__":
  resolve()
import sys

N, K = map(int, sys.stdin.readline())
L = sorted(list(map(int, sys.stdin.readline().split(" "))), reverse=True)
print(sum(L[0:K]))

### FIXED CODE ###

import sys
 
N, K = map(int, sys.stdin.readline().split(" "))
L = sorted(list(map(int, sys.stdin.readline().split(" "))), reverse=True)
print(sum(L[0:K]))
N, K = list(map(int, input().split()))

Snack = [0] * N

for i in range(K):
    d = int(input())
    A = list(map(int, input().split()))

    for j in range(d):
        Snack[A[j]] += 1
    
sum = 0
for i in range(N):
    if (Snack[i] == 0):
        sum += 1

print(sum)


### FIXED CODE ###

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

Snack = [0] * N

for i in range(K):
    d = int(input())
    A = list(map(int, input().split()))

    for j in range(d):
        Snack[A[j]-1] += 1
    
sum = 0
for i in range(N):
    if (Snack[i] == 0):
        sum += 1

print(sum)
n, m = map(int, input().split())

G = [[] for _ in range(m)]
for _ in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    G[u].append(v)
    G[v].append(u)

ans = [-1] * n
ans[0] = 'Yes'

from collections import deque

q = deque(G)

pos = 0
while q:
    _q = q.popleft()
    for x in _q:
        if ans[x] == -1:
            ans[x] = pos
    pos += 1

print('Yes')
for _ans in ans[1:]:
    print(_ans+1)


### FIXED CODE ###

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

G = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    G[u].append(v)
    G[v].append(u)

ans = [-1] * n

from collections import deque

q = deque([0])

while q:
    _q = q.popleft()
    for x in G[_q]:
        if ans[x] == -1:
            ans[x] = _q + 1
            q.append(x)

if -1 in ans:
    print('No')
else:
    ans[0] = 'Yes'
    for _ans in ans:
        print(_ans)
from collections import defaultdict

import math

from functools import lru_cache
#上手くいかない時は下
# from functools32 import lru_cache 

@lru_cache(None)
def prime_factorization_1(num):
    if num <= 1:
        return False
    else:
        num_sqrt = math.floor(math.sqrt(num))
        prime_list = make_prime_list_2(num_sqrt)

        dict_counter = defaultdict(int)
        for prime in prime_list:
            while num % prime == 0:
                dict_counter[prime] += 1
                num //= prime
        if num != 1:
            dict_counter[num] += 1

        dict_counter = dict(dict_counter)

        return dict_counter
def search_divisor_num_2(num):
    if num < 0:
        return None
    elif num == 1:
        return 1
    else:
        divisor_num = 1
        dict_fact = prime_factorization_1(num)
        for value in dict_fact.values():
            divisor_num *= (value + 1)
        return divisor_num
    
N=int(input())
cnt=0
for i in range(1,N):
    cnt += search_divisor_num_2(N-i)
    
print(cnt)

### FIXED CODE ###

N=int(input())

ans=0
for a in range(1,N):
    ans += (N-1)//a
print(ans)
import collections
n=int(input())
s = []
sort=[]
for i in range(n):
    s.append(input())
ans=collections.Counter(s).most_common()
oldnum=ans[0][1]
for i in range(n):
    if oldnum == ans[i][1]:
        sort.append(ans[i][0])
        oldnum=ans[i][1]
    else:
        break
sort.sort()
for i in range(len(sort)):
    print(sort[i])


### FIXED CODE ###

import collections
n=int(input())
s = []
sort=[]
for i in range(n):
    s.append(input())
ans=collections.Counter(s).most_common()
oldnum=ans[0][1]
for i in range(len(ans)):
    if oldnum == ans[i][1]:
        sort.append(ans[i][0])
        oldnum=ans[i][1]
    else:
        break
sort.sort()
for i in range(len(sort)):
    print(sort[i])
from operator import itemgetter
N=int(input())
listA=[[] for i in range(N)]
listANS=[]
for i in range(N):
  S,P=input().split()
  listA[i]+=[S,int(P),i+1]
listA.sort()
print(listA)
before=0
for i in range(1,N):
  if listA[i-1][0]!=listA[i][0]:
    listN=listA[before:i]
    listN.sort(key=itemgetter(1),reverse=True)
    listANS+=listN
    before=i

  if i==N-1:
    listN=listA[before:N]
    listN.sort(key=itemgetter(1),reverse=True)
    listANS+=listN

for i in range(N):
  print(listANS[i][2])

### FIXED CODE ###

from operator import itemgetter
N=int(input())
listA=[[] for i in range(N)]
listANS=[]
for i in range(N):
  S,P=input().split()
  listA[i]+=[S,int(P),i+1]
listA.sort()
before=0
if N!=1:
  for i in range(1,N):
    if listA[i-1][0]!=listA[i][0]:
      listN=listA[before:i]
      listN.sort(key=itemgetter(1),reverse=True)
      listANS+=listN
      before=i
 
    if i==N-1:
      listN=listA[before:N]
      listN.sort(key=itemgetter(1),reverse=True)
      listANS+=listN
else:
  listANS=listA
for i in range(N):
  print(listANS[i][2])
# D
import numpy as np
N = int(input())
X = np.zeros(N, dtype=int)
Y = np.zeros(N, dtype=int)

for i in range(N):
    x, y = map(int, input().split())
    X[i] = x
    Y[i] = y

# edges
X_s = np.argsort(X)
Y_s = np.argsort(Y)

edge_list = []
edge_weight = []
for i in range(N-1):
    edge_list.append([X_s[i], X_s[i+1]])
    edge_weight.append(min(abs(X[X_s[i+1]] - X[X_s[i]]), abs(Y[X_s[i+1]] - Y[X_s[i]])))
    edge_list.append([Y_s[i], Y_s[i+1]])
    edge_weight.append(min(abs(X[Y_s[i+1]] - X[Y_s[i]]), abs(Y[Y_s[i+1]] - Y[Y_s[i]])))
    
# sort edges
sel = np.argsort(np.array(edge_weight))

res = 0
flg = np.zeros(N)

for s in sel:
    m, n = edge_list[s]
    if flg[m]*flg[n] > 0:
        pass
    else:
        res += edge_weight[s]
        flg[m] = 1
        flg[n] = 1
print(res)

### FIXED CODE ###

# C
N, M = map(int, input().split())
L = 1000000007

res = 1

if (M - N) >= 2 or (N - M) >= 2:
    res = 0
else:
    for k in range(M):
        res *= (k+1)
        res = res % L
    for k in range(N):
        res *= (k+1)
        res = res % L
    if M == N:
        res *= 2
        res = res % L
print(res)
N = int(input())
A = list(map(int,input().split()))
A.sort()
B = []
for i in range(N):
    a = A.pop(0)
    B.append(0)
    B.append(0)
ans = 0
B.sort()
for i in range(N-1):
    a = B.pop(0)
    ans += b
print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
A.sort()
k = N - 2
a = A.pop()
ans = a
n = k // 2
for i in range(n):
    a = A.pop()
    ans += 2*a
if k - 2*n == 1:
    ans += A[-1]

print(ans)
n, m = map(int, input().split())
import math
pn = math.factorial(n) // (math.factorial(n-2) * math.factorial(2))
pm = math.factorial(m) // (math.factorial(m-2) * math.factorial(2))
p = pn + pm
print(p)

### FIXED CODE ###

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

p = n * (n - 1) // 2 + m * (m - 1) // 2

print(p)
def popcount(num):
    ans = 0
    while num:
        if num % 2 == 1:
            ans += 1
        num //= 2
    return ans

def first_popcount(X_i, pc):
    # bin_pc = ""
    # while pc:
    #     bin_pc = bin_pc + str(pc%2)
    #     pc //= 2
    
    # ans = 0
    # while 1:
    #     if len(X_i) <= len(bin_pc) and int(X_i, 2) < int(bin_pc, 2):
    #         break

    # return ans
    return int(X_i, 2) % pc

N = int(input())
X = input()

popcount_X = 0
for x in X:
    if x == "1":
        popcount_X += 1

tmp4p = first_popcount(X, popcount_X+1)
tmp4m = first_popcount(X, popcount_X-1)

for i in range(N):
    bit = X[i]

    f = 0
    if (popcount_X == 1 and bit == 1):
        print(f)
        continue
    
    if bit == "1":
        nxt = ( tmp4m - pow(2, N-i-1, (popcount_X-1))  + (popcount_X-1) ) % (popcount_X-1)
    else:
        nxt = ( tmp4p + pow(2, N-i-1, (popcount_X+1))  ) % (popcount_X+1)

    f += 1
    while nxt:
        pc = popcount(nxt)
        nxt = nxt % pc
        f += 1
    
    print(f)


### FIXED CODE ###

def popcount(num):
    ans = 0
    while num:
        if num % 2 == 1:
            ans += 1
        num //= 2
    return ans


N = int(input())
X = input()

popcount_X = 0
for x in X:
    if x == "1":
        popcount_X += 1

tmp4p = int(X, 2) % (popcount_X+1)
if popcount_X != 1:
    tmp4m = int(X, 2) % (popcount_X-1)

for i in range(N):
    bit = X[i]

    f = 0
    if (popcount_X == 1 and bit == "1"):
        print(f)
        continue
    
    if bit == "1":
        nxt = ( tmp4m - pow(2, N-i-1, (popcount_X-1))  + (popcount_X-1) ) % (popcount_X-1)
    else:
        nxt = ( tmp4p + pow(2, N-i-1, (popcount_X+1))  ) % (popcount_X+1)

    f += 1
    while nxt:
        pc = popcount(nxt)
        nxt = nxt % pc
        f += 1
    
    print(f)
n, m = map(int, input().split())
uv = [list(map(int, input().split())) for _ in range(m)]
s, t = map(int, input().split())

import heapq
from collections import defaultdict, deque
g1 = defaultdict(set)
for u, v in uv:
    g1[u-1].add(v-1)

s -= 1
t -= 1

dist = [[float('inf')] * 3 for _ in range(n)]
dist[s][0] = 0

q = [(0, s, 0)] # (dist, pos, kenken)
heapq.heapify(q)

while q:
    du, u, c = heapq.heappop(q)
    if dist[u][c] < du:
        continue
    c2 = (c + 1) % 3
    for v in g1[u]:
        if du + 1 < dist[v][c2]:
            dist[v][c2] = du + 1
            heapq.heappush(q, (dist[v][c2], v, c2))

if dist[t][0] != float('inf'):
    print(d)
else:
    print(-1)


### FIXED CODE ###

n, m = map(int, input().split())
uv = [list(map(int, input().split())) for _ in range(m)]
s, t = map(int, input().split())

import heapq
from collections import defaultdict
g1 = defaultdict(set)
for u, v in uv:
    g1[u-1].add(v-1)

s -= 1
t -= 1

dist = [[float('inf')] * 3 for _ in range(n)]
dist[s][0] = 0

q = [(0, s, 0)] # (dist, pos, kenken)
heapq.heapify(q)

while q:
    du, u, c = heapq.heappop(q)
    if dist[u][c] < du:
        continue
    c2 = (c + 1) % 3
    for v in g1[u]:
        if du + 1 < dist[v][c2]:
            dist[v][c2] = du + 1
            heapq.heappush(q, (dist[v][c2], v, c2))

if dist[t][0] != float('inf'):
    print(dist[t][0] // 3)
else:
    print(-1)
n,m = map(int,input().split())
tr = [[] for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    tr[a-1].append(b)
    tr[b-1].append(a)
if not tr[0]:
    print('No')
    exit()
else:
    mark = [10**7]*n
    mark[0] = -1
    cnt = 0
    i=0
    def mk(mark,i,cnt):
        for j in range(len(tr[i])):
            if tr[i][j]!=1:
                mark[tr[i][j]-1] = min(i+1,mark[tr[i][j]-1])
                cnt+=1
                if cnt == n-1:
                    return mark
            else:
                continue
        else:
            for j in range(len(tr[i])):
                mark = mk(mark,tr[i][j]-1,cnt)
            else:
                return mark
    mark=mk(mark,0,cnt)
    if 10**7 in mark:
        print('No')
    else:
        print('Yes')
        for i in range(1,n):
            print(mark[i])

### FIXED CODE ###

from collections import deque
 
n,m = list(map(int, input().split()))
put = [1]*(n+1)
 
ab = [[] for i in range(n+1)]
for i in range(m):
	a,b = map(int, input().split())
	ab[a].append(b)
	ab[b].append(a)

q = deque([1])
flg = [-1]*n
flg[0] = 0

while q:
	item = q.popleft()
	for i in ab[item]:
		if put[i]:
			flg[i-1]=item
			q.append(i)
			put[i]=0
 
if -1 in flg:
	print("No")
	exit()
 
print("Yes")
for i in range(1,len(flg)):
	print(flg[i])