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

import sys,os,io
input = sys.stdin.readline
# input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

N = int(input())
edge = [[] for _ in range(N)]
for i in range(N-1):
  a,b = list(map(int, input().split()))
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)
mod = 10**9+7
def comb_mod(n,r):
  ans = 1
  for i in range(r):
    ans *= (n-i)*pow(i+1,mod-2,mod)
    ans %= mod
  return ans
def combs_mod(n,k):
  #nC0からnCkまで
  ans = [1]*(k+1)
  for i in range(1,k+1):
    ans[i] = ans[i-1]*(n+1-i)*pow(i,mod-2,mod)%mod
  return ans

def dfs(start):
  stack = [start]
  parent = [N]*N
  parent[start] = -1
  while stack:
    v = stack[-1]
    marker = 0
    for u in edge[v]:
      if u==parent[v]:
        continue
      if parent[u]==N: #子へ降ろす
        marker = 1
        parent[u] = v
        stack.append(u)
      else: #子から吸い上げる
        part_num[v] += part_num[u]
        ans[v] *= comb_mod(part_num[v]-1, part_num[u])*ans[u]
        ans[v] %= mod
    if marker==0:
      stack.pop()
  return

def dfs2(start):
  stack = [start]
  parent = [N]*N
  parent[start] = -1
  p_value = [0]*N
  combs = combs_mod(N-1,N-1)
  while stack:
    v = stack.pop()
    for i,u in enumerate(edge[v]):
      if u==parent[v]:
        continue
      parent[u]=v
      p_value[u] = ans[v]*pow(ans[u]*combs[part_num[u]],mod-2,mod)%mod
      ans[u] *= combs[part_num[u]-1]*p_value[u]
      ans[u] %= mod
      stack.append(u)
    ans[v] %= mod
  return

ans = [1]*N
part_num = [1]*N
dfs(0)
dfs2(0)
print(*ans, sep='\n')

### FIXED CODE ###

import sys,os,io
input = sys.stdin.readline
# input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

N = int(input())
edge = [[] for _ in range(N)]
for i in range(N-1):
  a,b = list(map(int, input().split()))
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)
mod = 10**9+7

def fact(N):
  ans = [1]*(N+1)
  for i in range(1,N+1):
    ans[i] = ans[i-1]*i%mod
  return ans

def combs_mod(n,k):
  #nC0からnCkまで
  inv = [1]*(k+1)
  for i in range(1,k+1):
    inv[i] = pow(i,mod-2,mod)
  ans = [1]*(k+1)
  for i in range(1,k+1):
    ans[i] = ans[i-1]*(n+1-i)*inv[i]%mod
  return ans

def dfs(start):
  stack = [start]
  parent = [N]*N
  parent[start] = -1
  fac = fact(N)
  while stack:
    v = stack[-1]
    marker = 0
    for u in edge[v]:
      if u==parent[v]:
        continue
      if parent[u]==N: #子へ降ろす
        marker = 1
        parent[u] = v
        stack.append(u)
      else: #子から吸い上げる
        part_num[v] += part_num[u]
        ans[v] *= pow(fac[part_num[u]],mod-2,mod)*ans[u]%mod
        ans[v] %= mod
    if marker==0:
      stack.pop()
      ans[v] *= fac[part_num[v]-1]
      ans[v] %= mod
  return

def dfs2(start):
  stack = [start]
  parent = [N]*N
  parent[start] = -1
  p_value = [0]*N
  combs = combs_mod(N-1,N-1)
  while stack:
    v = stack.pop()
    for i,u in enumerate(edge[v]):
      if u==parent[v]:
        continue
      parent[u]=v
      p_value[u] = ans[v]*pow(ans[u]*combs[part_num[u]],mod-2,mod)%mod
      ans[u] *= combs[part_num[u]-1]*p_value[u]
      ans[u] %= mod
      stack.append(u)
  return

ans = [1]*N
part_num = [1]*N
dfs(0)
dfs2(0)
print(*ans, sep='\n')
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())
ga, sa, ba = map(int, input().split())
gb, sb, bb = map(int, input().split())
A = [10**18] * 3
B = [10**18] * 3
dg = abs(ga - gb)
ds = abs(sa - sb)
db = abs(ba - bb)
if ga < gb:
    A[0] = ga
elif ga > gb:
    B[0] = gb
if sa < sb:
    A[1] = sa
elif sa > sb:
    B[1] = sb
if ba < bb:
    A[2] = ba
elif ba > bb:
    B[2] = bb

def calc(X):
    res = -1
    for i in range(N+1):
        if X[0] * i > N:
            break
        M = N - X[0] * i
        jj = M // X[1]
        for j in range(max(jj - 500, 0), jj+1):
            k = (M - X[1] * j) // X[2]
            res = max(res, dg * i + ds * j + db * k)
        kk = M // X[2]
        for k in range(max(kk - 500, 0), kk+1):
            j = (M - X[2] * k) // X[1]
            res = max(res, dg * i + ds * j + db * k)
    return res

N += calc(A)
N += calc(B)
print(N)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
ga, sa, ba = map(int, input().split())
gb, sb, bb = map(int, input().split())
INF = 10**18
A = [INF] * 3
B = [INF] * 3
values = [abs(ga - gb), abs(sa - sb), abs(ba - bb)]
if ga < gb:
    A[0] = ga
elif ga > gb:
    B[0] = gb
if sa < sb:
    A[1] = sa
elif sa > sb:
    B[1] = sb
if ba < bb:
    A[2] = ba
elif ba > bb:
    B[2] = bb

def calc(X):
    dp = [0] * (N+1)
    dp[0] = 0
    for x, v in zip(X, values):
        for i in range(N+1-x):
            dp[i+x] = max(dp[i+x], dp[i] + v)
    return dp[-1]

N += calc(A)
N += calc(B)
print(N)
### BUGGY CODE ###

#最長増加部分列問題 (LIS) 
import bisect

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

LIS = [seq[0]]
#print(LIS)
for i in range(1, len(seq)):
    if seq[i] <= LIS[0]:
        LIS.insert(0, seq[i])
    else:
        LIS[bisect.bisect_left(LIS, seq[i]) - 1] = seq[i]
    #print(LIS)
#print(LIS)
print(len(LIS))

### FIXED CODE ###

#最長増加部分列問題 (LIS) 
import bisect

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

LIS = [-1] * N
LIS[-1] = seq[0]
#print(LIS)
for i in range(1, len(seq)):
    LIS[bisect.bisect_left(LIS, seq[i]) - 1] = seq[i]
    #print(LIS)
#print(LIS)
c = LIS.count(-1)
print(len(LIS) - c)
### BUGGY CODE ###

import bisect
import sys
import math
import itertools
sys.setrecursionlimit(10000)

INF = float('inf')

# input macro
def i():
    return int(raw_input())
def ii():
    return map(int,raw_input().split(" "))
def s():
    return raw_input()
def ss():
    return raw_input().split(" ")
def slist():
    return list(raw_input())
#

def join(s):
    return ''.join(s)

#iterate macro
def piter(n,m):
    return itertools.permutations(n,m)
def citer(n,m):
    return itertools.combinations(n,m)

#modulo macro
def modc(a,b,m):
    c = 1
    for i in xrange(b):
        c = c * (a - i) % m
        c = c * modinv(i + 1,m) % m
    return c
 
def gcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
 
def modinv(a, m):
    (inv, q, gcd_val) = gcd(a, m)
    return inv % m

#bisect macro
def index(a, x):
    #Locate the leftmost value exactly equal to x
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    return -1

#memoize macro
def memoize(f):
    cache = {}
    def helper(*args):
        if args not in cache:
            cache[(args)] = f(*args)
        return cache[args]
    return helper

@memoize
def nck(a,b,m):
    b = min([a-b,b])
    if (b>a or b<0 or a<0):
        return 0
    elif a == 0:
        return 1
    return (nck(a-1,b-1,m)+nck(a-1,b,m)) % m

nh=zip([1,0,-1,0],[0,1,0,-1])

###########

n,x=ii()
a=ii()

@memoize
def dp(j,k):
    if k!=0:
        return min(dp(j,k-1),a[(j-k)%n])
    else:
        return a[j]

print min([sum([dp(j,k) for j in range(n)])+k*x for k in range(n)])


### FIXED CODE ###

n,x=map(int,raw_input().split(" "))
a=map(int,raw_input().split(" "))
t=[i for i in a]
s=10**15
for m in range(n):
    t=[min(t[j],a[(j-m)%n]) for j in range(n)]
    s=min(x*m+sum(t),s)
print s
### BUGGY CODE ###

n,k = (int(a) for a in input().split())
A = list(map(int,input().split()))
t = [1]
x = 1
while len(t) == len(set(t)) :
    t.append(A[x-1])
    x = t[-1] 
l = [i for i , x in enumerate(t) if x == t[-1]]
if k < l[0] :
    print(t[k])
else :
    k = k-l[0]
    ans = k%(l[1]-l[0])
    print(t[l[0] + ans])

### FIXED CODE ###

n,k = (int(a) for a in input().split())
A =  [-1] + list(map(int,input().split()))
t = [1]
flag =[0,1] + [0]*(n-1)
x = A[1]
while flag[x] == 0 :
    t.append(x)
    flag[x] = 1
    x = A[x] 

if k <= len(t) -1 :
    print(t[k])
else :
    l = t[t.index(x):]
    k = k - (len(t) - 1)
    k %= len(l)
    print(l[k-1])
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n):
    a[i] -= 1

doubling = []
lst = []
for i in range(n):
    lst.append(a[i])
doubling.append(lst)

for i in range(59):
    before = doubling[-1]
    after = []
    for j in range(n):
        after.append(before[before[j]])
    doubling.append(after)

sisu = 59
now = 0
while k > 0:
    idx = pow(2, sisu)
    if k < idx:
        sisu -= 1
    else:
        k -= idx
        now = doubling[sisu][now]
print(now+1)

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n):
    a[i] -= 1

already = [-1 for i in range(n)]
already[0] = 0
mati = 0
num = 0
for _ in range(n):
    num += 1
    mati = a[mati]
    if already[mati] == -1:
        already[mati] = num
        continue
    else:
        roop = num - already[mati]
        break

saisho = already[mati]
if k <= saisho:
    tugi = 0
    for _ in range(k):
        tugi = a[tugi]
    print(tugi+1)
else:
    nokori = k - saisho
    amari = nokori % roop
    for _ in range(amari):
        mati = a[mati]
    print(mati+1)
### BUGGY CODE ###

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

ans = 0
for i in range(n - 1, 0, -1):
    x = 1
    while i + x < n and hh[i + x - 1] >= hh[i + x]:
        x += 1
    ans = max(ans, x - 1)
print(ans)


### FIXED CODE ###

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

ans = 0
x = 0
for i in range(1, n):
    if h[i - 1] >= h[i]:
        x += 1
    else:
        x = 0
    ans = max(ans, x)
print(ans)
### BUGGY CODE ###

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



for i in range(0,a[0]*2+1,2):
    ans = [0]*n
    ans[0] = i
    for j in range(1,n):
        tmp = (a[j-1]-ans[j-1]//2)*2
        ans[j] = tmp
    if (ans[-1]/2 + ans[0]/2) == a[-1]:
        print(*ans)
        exit()



### FIXED CODE ###

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

s = sum(a)
s1 = 0
for i in range(1,n,2):
    s1 += a[i]

ans = [s-s1*2]
for i in range(1,n):
    ans.append((a[i-1]-ans[i-1]//2)*2)

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

#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def f(a, s, n):
    if s[-1] == "1":
        return 1

    st = {0,}
    for i in range(n-1, -1, -1):
        ai, si = a[i], s[i]

        if si == "0":
            tmp = [ai ^x for x in st]
            st.update(tmp)
        else:
            if ai in  st:
                st.remove(ai)
            else:
                return 1
    return 0


def resolve():
    T = int(input())

    ans = []
    for i in range(T):
        N = int(input())
        A = list(iim())
        S  = input()

        ans.append(f(A, S, N))

    print(*ans, sep="\n")

if __name__ == "__main__":
    resolve()


### FIXED CODE ###

#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

X = (10**18).bit_length()

def f(a, s, n):
    if s[-1] == "1":
        return 1

    B = [None] * X
    for i in range(n-1, -1, -1):
        ai, si = a[i], s[i]

        if si == "0":
            while True:
                x = ai.bit_length() - 1
                if B[x] == ai: break
                elif B[x] == None:
                    B[x] = ai
                    break
                ai ^= B[x]
        else:
            while True:
                x = ai.bit_length() - 1
                if B[x] == ai: break
                elif B[x] == None:
                    return 1
                ai ^= B[x]
    return 0


def resolve():
    T = int(input())

    ans = []
    for i in range(T):
        N = int(input())
        A = list(iim())
        S  = input()

        ans.append(f(A, S, N))

    print(*ans, sep="\n")

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

n = int(input())
a = [int(i) for i in input().split(" ")]
q = int(input())

operations = []

for i in range(q):
    temp = input().split(" ")
    operations.append((int(temp[0]), int(temp[1])))

for op in operations:
    target, goto = op

    a.sort()

    try:
        index = a.index(target)
        
        while True:
            if a[index] != target:
                break

            a[index] = goto
            index += 1

        print(sum(a))

    except:
        print(sum(a))

    #for i in range(len(a)):
    #    if a[i] == target:
    #        a[i] = goto

    #print(sum(a))

### FIXED CODE ###

from collections import defaultdict

d = defaultdict(int)

n = int(input())
a = [int(i) for i in input().split(" ")]
q = int(input())

operations = []

for i in range(q):
    temp = input().split(" ")
    operations.append((int(temp[0]), int(temp[1])))

for hoge in a:
    d[hoge] += 1

initial_sum = 0
for key, value in d.items():
    initial_sum += key * value

for op in operations:
    target, goto = op

    before = goto * d[goto] + target * d[target]
    d[goto] += d[target]
    d[target] = 0

    after = goto * d[goto]
    diff = after - before
    
    initial_sum += diff
    print(initial_sum)
### BUGGY CODE ###

n,k = map(int,input().split())
p = [int(i) for i in input().split()]
count = 0

for i in range(n):
    if i+k < n:
        if p[i] <= min(p[i:i+k]) and p[i+k] >= max(p[i+1:i+k]):
            count += 1
        elif p[i:i+k] == sorted(p[i:i+k]):
            count += 1

print(n-k+1-count)

### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(N)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """

    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, left, right):
        """
        [left, right)のsegfuncしたものを得る
        left: index(0-index)
        right: index(0-index)
        """
        res = self.ide_ele
        left += self.num
        right += self.num
        while left < right:
            if left & 1:
                res = self.segfunc(res, self.tree[left])
                left += 1
            if right & 1:
                res = self.segfunc(res, self.tree[right - 1])
            left >>= 1
            right >>= 1
        return res


def resolve():
    n, k = map(int, input().split())
    P = list(map(int, input().split()))

    seg_min = SegTree(P, lambda x, y: min(x, y), f_inf)
    seg_max = SegTree(P, lambda x, y: max(x, y), -f_inf)
    mi = seg_min.query(0, k)
    ma = seg_max.query(0, k)
    res = {(0, k - 1)}
    for i in range(1, n - k + 1):
        prev = P[i - 1]
        new = P[i + k - 1]
        if prev != mi or new < ma:
            res.add((i, i + k - 1))
        mi = seg_min.query(i, i + k)
        ma = seg_max.query(i, i + k)

    ascending = []
    head = 0
    foot = 1
    cnt = 1
    for i in range(1, n):
        if P[i - 1] < P[i]:
            cnt += 1
            foot = i
        else:
            cnt = 1
            head = i
        if cnt == k:
            ascending.append((head, foot))
            head = i
            cnt -= 1

    ans = len(res)
    flg = False
    for section in ascending:
        if section in res:
            if not flg:
                flg = True
            else:
                ans -= 1
    print(ans)


if __name__ == '__main__':
    resolve()
### BUGGY CODE ###

from math import log2

N, K = map(int, input().split())
A = [int(s) for s in input().split()]


def cntbit(bit):
    cnt = 0
    for a in A:
        if a & bit:
            cnt += 1
    return cnt


def getans(bink):
    if len(bink) == 1:
        if bink == "0":
            return cntbit(1)
        else:
            return N - cntbit(1)

    ans = 0
    bit = 1 << (len(bink) - 1)
    if bink[0] == "0":
        return bit * cntbit(bit) + getans(bink[1:])
    else:
        ans1 = bit * (N - cntbit(bit)) + getans(bink[1:])
        ans2 = 0
        ans2 += bit * cntbit(bit)
        for i in range(len(bink) - 1):
            bit = 1 << i
            cnt = cntbit(bit)
            ans2 += bit * max(cnt, N - cnt)
        return max(ans1, ans2)


bink = bin(K)[2:]
bink = "0" * (40 - len(bink)) + bink
print(getans(bink))


### FIXED CODE ###

N, K = map(int, input().split())
A = [int(s) for s in input().split()]


def cntbit(bit):
    cnt = 0
    for a in A:
        if a & bit:
            cnt += 1
    return cnt


def getans(bink):
    if len(bink) == 1:
        if bink == "0":
            return cntbit(1)
        else:
            return N - cntbit(1)

    ans = 0
    bit = 1 << (len(bink) - 1)
    if bink[0] == "0":
        return bit * cntbit(bit) + getans(bink[1:])
    else:
        ans1 = bit * (N - cntbit(bit)) + getans(bink[1:])
        ans2 = 0
        ans2 += bit * cntbit(bit)
        for i in range(len(bink) - 1):
            bit = 1 << i
            cnt = cntbit(bit)
            ans2 += bit * max(cnt, N - cnt)
        return max(ans1, ans2)


bink = bin(K)[2:]
bink = "0" * (40 - len(bink)) + bink
print(getans(bink))
### BUGGY CODE ###

def function(a):
    for j in range(2,a):
        if a%j==0:
            return 1
    return 0
n=int(input())
s=0
for i in range(n):
    a=int(input())
    s+=function(a)
print(n-s)


### FIXED CODE ###

def function(a):
    for j in range(2,a):
        if a%j==0:
            return 1
        if j**2>a:
            break
    return 0
n=int(input())
s=0
for i in range(n):
    a=int(input())
    s+=function(a)
print(n-s)
### BUGGY CODE ###

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

a.sort(reverse = True)

cnt = [[a[i]] for i in range(n)]

for i in range(n):
    while 1:
        a[i] = a[i] // 2
        cnt[i].append(a[i])
        if a[i] == 0:
            break
while m > 0:
    max_num = [cnt[i][0] for i in range(n)]
    max_index = max_num.index(max(max_num))
    if cnt[max_index][0] == 0:
        break
    del cnt[max_index][0]
    m -= 1
max_num = [cnt[i][0] for i in range(n)]
print(sum(max_num))

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
a = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(a)

while m > 0:
    a_max = heapq.heappop(a)
    if a_max == 0:
        break
    heapq.heappush(a, (-1)*(-a_max // 2))
    m -= 1
print(sum(a)*(-1))
### BUGGY CODE ###

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

def sumcmb(T):
    count=0
    m=T
    while m>=0:
        count+=cmb(T,m)
        T-=1
        m-=2
    return(count)


N,M=map(int,input().split())
A=[int(input()) for i in range(M)]
mod=10**9+7
for i in range(M-1):
    if A[i]+1==A[i+1]:
        print(0)
        exit()

if 1 not in A:
    A.insert(0,-1)
if N not in A:
    A.append(N+1)


count=1
for i in range(len(A)-1):
    T=max(A[i+1]-1 - (A[i]+1),1)
    #print(sumcmb(T))
    count*=sumcmb(T)
    if count>mod:
        count%=mod
print(count)


### FIXED CODE ###

N,M=map(int,input().split())
mod=10**9+7
A=set([int(input()) for i in range(M)])

data=[0 for i in range(N)]
if 1 not in A:
    data[0]=1
if N>=2:
    if 2 not in A:
        data[1]=1+data[0]


for i in range(2,N):
    if i+1 not in A:
        data[i]=data[i-1]+data[i-2]
        data[i]%=mod

#print(data)

print(data[-1])
### BUGGY CODE ###

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

k = int(input())
res = 0
for i in range(1, k+1):
    for j in range(1, k+1):
        for m in range(1, k+1):
            res += gcd_(gcd_(i, j), m)

print(res)


### FIXED CODE ###

from math import gcd

k = int(input())
res = 0
for i in range(1, k+1):
    for j in range(1, k+1):
        for m in range(1, k+1):
            res += gcd(gcd(i, j), m)

print(res)
### BUGGY CODE ###

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

mv_scores = []
for i in range(k, n+1):
    tmp_score = 1
    for s in score[i-k:i]:
        tmp_score *= s
    mv_scores.append(tmp_score)

for j in range(1, len(mv_scores)):
    if mv_scores[j] - mv_scores[j-1] > 0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

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

for i in range(k, n):
    if score[i-k] < score[i]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

while True:
    c = 0
    n, x= map(int, input().split())
    if n == 0 and x == 0:
        break
    for i in range(1, n + 1):
        for j in range(1, n + 1 ):
            for k in range(1, n + 1):
                if i != j and i != k and j != k and i + j + k == x:
                    c += 1
    print(c // 6)


### FIXED CODE ###

while True:
    c = 0
    n, x= map(int, input().split())
    if n == 0 and x == 0:
        break
    for i in range(1, n + 1):
        for j in range(1, n + 1 ):
            if j <= i:
                continue
            for k in range(1, n + 1):
                if k <= j:
                    continue
                if i != j and i != k and j != k and i + j + k == x:
                    c += 1
    print(c)
### BUGGY CODE ###

N,W = [int(i) for i in input().split()]
wv = [[int(i) for i in input().split()] for j in range(N)]
dp = [[0]*(W+1) for i in range(N+1)]
for i in range(1, N+1):
    for j in range(1, W+1):
        if 0 <= j-wv[i-1][0]:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-wv[i-1][0]] + wv[i-1][1])
        else:
            dp[i][j] = dp[i-1][j]
print(dp[-1][-1])

### FIXED CODE ###

N,W = [int(i) for i in input().split()]
wv = [[int(i) for i in input().split()] for j in range(N)]
dp = [[0]*(W+1) for i in range(N+1)]
for i in range(1, N+1):
    for j in range(1, W+1):
        if 0 <= j-wv[i-1][0]:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-wv[i-1][0]] + wv[i-1][1])
        else:
            dp[i][j] = dp[i-1][j]
print(dp[-1][-1])
### BUGGY CODE ###

from collections import deque
n,m = map(int, input().split())
t = [[] for i in range(n)]
dis = [n for i in range(n)]
dis[0] = 0
near = [0 for i in range(n)]
q = deque()
for i in range(m):
    a,b = map(int, input().split())
    t[a-1].append(b-1)
    t[b-1].append(a-1)
for i in range(len(t[0])):
    c = t[0][i]
    dis[c] = 1
    near[c] = 0
    q.append(c)
while len(q) > 0:
    e = q.popleft()
    for j in range(len(t[e])):
        c = t[e][j]
        if dis[c] >= dis[e] +1:
            dis[c] = dis[e] +1
            near[c] = e
            q.append(c)
print('Yes')
for i in range(1,len(near)):
    print(near[i]+1)


### FIXED CODE ###

from collections import deque
n,m = map(int, input().split())
t = [[] for i in range(n)]
near = [-1 for i in range(n)]
near[0] = 0
q = deque()
for i in range(m):
    a,b = map(int, input().split())
    t[a-1].append(b-1)
    t[b-1].append(a-1)
for i in range(len(t[0])):
    c = t[0][i]
    near[c] = 0
    q.append(c)
while len(q) > 0:
    e = q.popleft()
    for j in range(len(t[e])):
        c = t[e][j]
        if near[c] == -1:
            near[c] = e
            q.append(c)
print('Yes')
for i in range(1,len(near)):
    print(near[i]+1)