Harryxun/stf_run huggingface dataset:
#!/usr/bin/env python
# coding: utf-8

# In[1]:


import sys
import numpy as np
import itertools
input = sys.stdin.readline
N, M = map(int, input().split())
l = [list(map(int, input().split())) for i in range(M+1)]


# In[ ]:


"""
5 2
3 1 2 5
2 2 3
1 0
"""


# In[4]:


#print(l)
import numpy as np


# In[7]:


s = range(N)
cnt = 0
for e in range(1, N+1):
    c = list(itertools.combinations(s,e))
    #print(c)
    #print(c)
    o = list(range(N))
    for b in c:
        #print(b)
        a = np.zeros((N))
        for d in b:
            a[d] = 1
        #print(a)
        for i in range(M):
            sum_ = 0
            for j in range(len(l[i][1:])):
                ind = l[i][j+1]-1
                #print(ind)
                sum_ += a[ind]
            o[i] = sum_%2==l[-1][i]
        if np.all(o):
            cnt += 1
print(cnt)


# In[ ]:


"""
2 2
2 1 2
1 2
0 1
"""



### FIXED CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[12]:


import sys
#import numpy as np
import itertools
input = sys.stdin.readline
N, M = map(int, input().split())
l = [list(map(int, input().split())) for i in range(M+1)]


# In[ ]:


"""
5 2
3 1 2 5
2 2 3
1 0
"""


# In[4]:


#print(l)
#import numpy as np


# In[15]:


cnt = 0
#print(itertools.product(range(0, 2), repeat=N))
for on in itertools.product(range(0, 2), repeat=N):
    for i in range(M):
        sum_ = 0
        for j in range(l[i][0]):
            ind = l[i][j+1]-1
            sum_ += on[ind]
        if sum_%2 != l[-1][i]:
            break
    else:
        cnt += 1
print(cnt)

"""
s = range(N)
cnt = 0
# N個がonになる
for e in range(1, N+1):
    c = list(itertools.combinations(s,e))# N個onになる通り
    o = list(range(N))
    for b in c:
        #print(b)
        a = np.zeros((N))
        for d in b:
            a[d] = 1
        #print(a)
        for i in range(M):
            sum_ = 0
            for j in range(l[i][0]):
                ind = l[i][j+1]-1
                #print(ind)
                sum_ += a[ind]
            o[i] = sum_%2==l[-1][i]
        if np.all(o):
            cnt += 1
#0個on
o = list(range(N))
a = np.zeros((N))
for i in range(M):
    sum_ = 0
    for j in range(l[i][0]):
        ind = l[i][j+1]-1
        sum_ += a[ind]
    o[i] = sum_%2==l[-1][i]
if np.all(o):
    cnt += 1
print(cnt)
"""


# In[ ]:


"""
2 2
2 1 2
1 2
0 1
"""
m,d=int(input()),input()
M,D=int(input()),input()

if M - m == 1:
  print('1')
else:
  print('0')

### FIXED CODE ###

m=input().split()
M=input().split()
 
if int(M[0]) - int(m[0]) == 1:
  print('1')
else:
  print('0')
ls = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
num = scan()
print(ls[int(num)])

### FIXED CODE ###

ls = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
num = input()
print(ls[int(num)-1])
S = list(input())
T = list(input())
N = len(S)
M = len(T)
l = []
flag = 0
exist = 0
for i in range(N-M+1):
    flag = 0
    for j in range(M):
        if T[j] != S[i+j] and S[i+j] != "?":
            flag += 1

    if flag == 0:
        tmp = S.copy()
        for k in range(M):
            tmp[i+k] = T[k]
        l.append(tmp)
        exist = 1

a = []
if exist == 1: 
    L = len(l)
    for i in range(L):
        tmp = l[i].copy()
        for j in range(N):
            if tmp[j] == "?":
                tmp[j] = "a"
        a.append(tmp)
    a.sort()
    ans = "".join(a[0])
    print(ans)
else:
    print("UNRESTORABLE")

### FIXED CODE ###

from copy import copy
S = list(input())
T = list(input())
N = len(S)
M = len(T)
l = []
flag = 0
exist = 0
for i in range(N-M+1):
    flag = 0
    for j in range(M):
        if T[j] != S[i+j] and S[i+j] != "?":
            flag += 1

    if flag == 0:
        tmp = copy(S)
        for k in range(M):
            tmp[i+k] = T[k]
        l.append(tmp)
        exist = 1

a = []
if exist == 1: 
    L = len(l)
    for i in range(L):
        tmp = copy(l[i])
        for j in range(N):
            if tmp[j] == "?":
                tmp[j] = "a"
        a.append(tmp)
    a.sort()
    ans = "".join(a[0])
    print(ans)
else:
    print("UNRESTORABLE")
n = int(input())
A = list(map(int,input().split()))
m = int(input())
B = list(map(int,input().split()))

def solve(x,y):
    if y<0:    return False
    elif y==0:  return True
    elif x==n:  return False
    else:
        return solve(x+1,y-A[x]) or solve(x+1,y)
    
for i in range(m):
    if solve(0,B[i]): print("yes") 
    else: print("no")



### FIXED CODE ###

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

T = [[0]*2001 for i in range(n)]

T[0][0] = 1
T[0][A[0]] = 1
for i in range(1,n):
    for j in range(2001):
        T[i][j] = T[i-1][j]
        if (j - A[i] >=0) and (T[i-1][j-A[i]] == 1):
            T[i][j] = 1
    
for i in range(m):
    if T[n-1][B[i]] == 1: print("yes")
    else: print("no")
def check_ans(s,x):
  for i in range(0,2**len(s)):
    ans=0
    for j in range(len(s)):
      if (i>>j)%2:
        ans+=s[j]
      else:
        ans-=s[j]
    if ans==x:
      return True
  return False

S=input()
X,Y=map(int,input().split())
d=1
while S[0]=='F':
  S=S[1:]
  X-=1
nx=[]
ny=[]

while S:
  step=0
  while S and S[0]=='T':
    d*=-1
    S=S[1:]
  while S and S[0]=='F':
    step+=1
    S=S[1:]
  if d==1:
    nx.append(step)
  else:
    ny.append(step)
  if len(S)==1:
    break

if check_ans(nx,X) and check_ans(ny,Y):
  print("Yes")
else:
  print("No")

### FIXED CODE ###

import sys

def check_ans(s,x):
  res=[0]
  for i in s:
    res = set([x + i for x in res]) | set([x - i for x in res])
  return x in res

S = sys.stdin.readline().strip()
X,Y=map(int,input().split())
d=1
while S and S[0]=='F':
  S=S[1:]
  X-=1
if len(S)==0:
  if X==0 and Y==0:
    print("Yes")
  else:
    print("No")
  sys.exit()

nx=[]
ny=[]
X=abs(X)
Y=abs(Y)

while S:
  step=0
  while S and S[0]=='T':
    d*=-1
    S=S[1:]
  while S and S[0]=='F':
    step+=1
    S=S[1:]
  if step==0:
    break
  if d==1:
    nx.append(step)
  else:
    ny.append(step)

if check_ans(nx,X) and check_ans(ny,Y):
  print("Yes")
else:
  print("No")
S = input()
print(ans)
for i in range(4):
  if S[i] == "+":
    ans += 1
  else:
    ans -= 1
print(ans)

### FIXED CODE ###

S = input()
ans = 0
for i in range(4):
  if S[i] == "+":
    ans += 1
  else:
    ans -= 1
print(ans)
# ABC073D - joisino's travel
from heapq import heapify, heappop, heappush
from itertools import permutations


def dijkstra(G: "Array[Array[int]]", size: int, start: int) -> list:
    dist = [float("inf")] * size
    searched = [0] * size
    dist[start], searched[start] = 0, 1
    queue = G[start]
    heapify(queue)
    while queue:
        v, cost = heappop(queue)
        if searched[v] or cost > dist[v]:
            continue
        dist[v] = cost
        searched[v] = 1
        for u, next_cost in G[v]:
            if cost + next_cost < dist[u]:
                heappush(queue, (u, cost + next_cost))
    return dist


def main():
    global G, N
    N, M, R, *RABC = map(int, open(0).read().split())
    visit, ABC = RABC[:R], RABC[R:]
    G = [[] for _ in range(N + 1)]
    for v, u, c in zip(*[iter(ABC)] * 3):
        G[v].append((u, c)), G[u].append((v, c))
    dist = [None] + [dijkstra(G, N + 1, i) for i in range(1, N + 1)]
    ans = float("inf")
    for perm in permutations(visit):
        cur = sum(dist[v][u] for v, u in zip(perm, perm[1:]))
        ans = min(ans, cur)
    print(int(ans))


if __name__ == "__main__":
    main()

### FIXED CODE ###

# ABC073D - joisino's travel
from itertools import permutations
from scipy.sparse.csgraph import floyd_warshall


def main():
    N, M, R, *RABC = map(int, open(0).read().split())
    visit, ABC = RABC[:R], RABC[R:]
    G = [[float("inf")] * (N + 1) for _ in range(N + 1)]
    for v, u, c in zip(*[iter(ABC)] * 3):
        G[v][u] = G[u][v] = c
    dist = floyd_warshall(G, directed=0)
    ans = float("inf")
    for perm in permutations(visit):
        cur = sum(dist[v][u] for v, u in zip(perm, perm[1:]))
        ans = min(ans, cur)
    print(int(ans))


if __name__ == "__main__":
    main()
a = list(map(int,input().split()))
d = abs(a[0] - a[2])
d1 = abs(a[0] - a[1])
d2 = abs(a[1] - a[2])
if d <= a[3]:
  print("Yes")
elif d1 <= a[3] or d2 <= a[3]:
  print("Yes")
elif a[0] = a[1] and a[0] = a[2]:
  print("Yes")
else: print("No")

### FIXED CODE ###

a = list(map(int,input().split()))
d = abs(a[0] - a[2])
d1 = abs(a[0] - a[1])
d2 = abs(a[1] - a[2])

if d <= a[3]:
  print("Yes")
elif d1 <= a[3] and d2 <= a[3]:
  print("Yes")
else: print("No")
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    H,W = LI()
    ch, cw = _LI()
    dh, dw = _LI()
    m = [[0] * W for _ in range(W)]
    for i in range(H):
        s = SI()
        for j in range(W):
            if s[j] == "#":
                m[i][j] = -1

    z = [(ch,cw,1)]
    while z:
        x,y,c = z.pop()
        q = collections.deque()
        q.append((x,y))
        m[x][y] = c
        r = [(x,y)]
        while q:
            x,y = q.popleft()
            if x == dh and y == dw:
                print(c-1)
                return
            for dx,dy in ((0,1),(1,0),(-1,0),(0,-1)):
                nx = x + dx
                ny = y + dy
                if not(0<= nx < H and 0<= ny < W): continue
                if m[nx][ny]: continue
                m[nx][ny] = c
                q.append((nx,ny))
                r.append((nx,ny))
        for x,y in r:
            for dx in range(-2,3):
                nx = x + dx
                if not(0<= nx < H): continue
                for dy in range(-2,3):
                    ny = y + dy
                    if not(0<= ny < W): continue
                    if m[nx][ny]: continue
                    z.append((nx,ny,c+1))
    print(-1)
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    H,W = LI()
    ch, cw = _LI()
    dh, dw = _LI()
    m = [[0] * W for _ in range(H)]
    for i in range(H):
        s = SI()
        for j in range(W):
            if s[j] == "#":
                m[i][j] = -1

    z = collections.deque()
    z.append((ch,cw,1))
    while z:
        x,y,c = z.popleft()
        if m[x][y]: continue
        q = collections.deque()
        q.append((x,y))
        m[x][y] = c
        r = [(x,y)]
        while q:
            x,y = q.popleft()
            if x == dh and y == dw:
                print(c-1)
                return
            for dx,dy in ((0,1),(1,0),(-1,0),(0,-1)):
                nx = x + dx
                ny = y + dy
                if not(0<= nx < H and 0<= ny < W): continue
                if m[nx][ny]: continue
                m[nx][ny] = c
                q.append((nx,ny))
                r.append((nx,ny))
        for x,y in r:
            for dx in range(-2,3):
                nx = x + dx
                if not(0<= nx < H): continue
                for dy in range(-2,3):
                    ny = y + dy
                    if not(0<= ny < W): continue
                    if m[nx][ny]: continue
                    z.append((nx,ny,c+1))
    print(-1)
if __name__ == '__main__':
    main()
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np 
def main():
    A = np.arange(1, int(readline()), dtype=np.int64)
    print(A.sum())
if __name__ == '__main__':
    main()


### FIXED CODE ###

#python3
n=int(input())
n-=1
print(n*(n+1)//2)
# -*- coding: utf-8 -*-
A,B,C=map(int,input().split())
S =[A,B,C]
T =[5,5,7]
if S = T:
  print("YES")
else:
  print("NO")

### FIXED CODE ###

# -*- coding: utf-8 -*-
A,B,C = map(str,input().split())
S = A+B+C
if S.count("5") ==2 and S.count("7") == 1:
  print("YES")
else:
  print("NO")
def findTrailingZeroes(n):
       if(n & 1):
           return 0
       else:
              ans=0
              n //=2
              while(n):
                      ans +=n//5
                      n//=5
               return ans
n=12
print(findTrailingZeroes(n))

### FIXED CODE ###

p=int(input())
n=p
if n%2 == 0:
    num=10
    c=0;
    while num <= n:
        c += (n//num)
        num *= 5
    print(c)
else:
    print(0)
n, k = map(int,input().split())
ans = 0
if n < k:
    ans = n
else:
    ans = min(n%k,k-n%k))

print(ans)


### FIXED CODE ###

n, k = map(int,input().split())
ans = 0
ans = min(n%k,abs(n%k-k))

print(ans)
N = int(input())
A = list(map(int,input().split()))
b = sorted([b-i for i,b in enumerate(A,1)])

minus = 0
plus = 0
for i,c in enumerate(b,1):
    if c <0:
        minus +=1
    elif c >0:
        plus +=1

m = b[(N-minus+plus)//2]
out = sum([abs(c-m) for c in b])
print(out)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
b = sorted([a-i for i,a in enumerate(A,1)])

minus = 0
plus = 0
for c in b:
    if c <0:
        minus +=1
    elif c >0:
        plus +=1

m1 = b[N//2]
m2 = b[0] if N==1 else b[N//2+1]
out = min(sum([abs(c-m1) for c in b]),sum([abs(c-m2) for c in b]))
print(out)
import sys

n,A,B,C=map(int,input().split())
x=list(set(map(int,sys.stdin)))

inf=10**9

def dfs(cur,a,b,c):
    if cur==n:
        #print("abs",abs(a-A),abs(b-B),abs(c-C))
        #print("abs...",abs(a-A)+abs(b-B)+abs(c-C)-30)
        return abs(a-A)+abs(b-B)+abs(c-C)-30 if min(a,b,c)>0 else inf
    ret0 = dfs(cur+1,a,b,c)
    ret1 = dfs(cur+1,a+x[cur],b,c) + 10
    ret2 = dfs(cur+1,a,b+x[cur],c) + 10
    ret3 = dfs(cur+1,a,b,c+x[cur]) + 10
    #print(ret0,ret1,ret2,ret3)
    return min(ret0, ret1, ret2, ret3)

print(dfs(0,0,0,0))

### FIXED CODE ###

import sys

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

x=[int(input()) for _ in range(n)]
inf=10**9

def dfs(cur,a,b,c):
    if cur==n:
        #print("abs",abs(a-A),abs(b-B),abs(c-C))
        #print("abs...",abs(a-A)+abs(b-B)+abs(c-C)-30)
        return abs(a-A)+abs(b-B)+abs(c-C)-30 if min(a,b,c)>0 else inf
    ret0 = dfs(cur+1,a,b,c)
    ret1 = dfs(cur+1,a+x[cur],b,c) + 10
    ret2 = dfs(cur+1,a,b+x[cur],c) + 10
    ret3 = dfs(cur+1,a,b,c+x[cur]) + 10
    #print(ret0,ret1,ret2,ret3)
    return min(ret0, ret1, ret2, ret3)

print(dfs(0,0,0,0))
s = input() + "R"
v = [0 for i in range(len(s)-1)]

even = 0
odd = 0
lrpos = 0
lr = "R"

for i in range(len(s)):
    if lr != s[i]:
        if lr == "R":
            if even == odd:
                v[i-1] += even
                v[i] += odd
            else:
                v[i] += even
                v[i-1] += odd
        else:
            if even == odd:
                v[lrpos] += even
                v[lrpos-1] += odd
            else:
                v[lrpos-1] += even
                v[lrpos] += odd
        
        odd = 0
        even = 0
        lr = s[i]
        lrpos = i

    if even < odd:
        even += 1
    else:
        odd += 1
    
ans = " ".join(v)
print(ans)


### FIXED CODE ###

s = input() + "R"
v = [0 for i in range(len(s)-1)]

even = 0
odd = 0
lrpos = 0
lr = "R"

for i in range(len(s)):
    if lr != s[i]:
        if lr == "R":
            if even == odd:
                v[i-1] += even
                v[i] += odd
            else:
                v[i] += even
                v[i-1] += odd
        else:
            if even == odd:
                v[lrpos] += even
                v[lrpos-1] += odd
            else:
                v[lrpos-1] += even
                v[lrpos] += odd
        
        odd = 0
        even = 0
        lr = s[i]
        lrpos = i

    if even < odd:
        even += 1
    else:
        odd += 1
    
ans = " ".join(map(str,v))
print(ans)
from scipy.sparse import*
(n,m,s,*D),*t=[map(int,t.split())for t in open(0)]
R,C=[],[]
r=range(2501)
for u,v,a,b in t[:m]:
 for i in r:k=(i+a)*51;R+=k+u,k+v;C+=i*51+v,i*51+u;D+=b,b
for i,(c,d)in enumerate(t[m:],1):
 for j in r:R+=j*51+i,;C+=(j+c)*51+i,;D+=d,
d=csgraph.dijksta(csr_matrix((D,(R,C))),1,min(2500,s)*51+1)
for i in range(2,n+1):print(int(min(d[i::51])))

### FIXED CODE ###

from scipy.sparse import*
n,m,s,*t=map(int,open(0).read().split())
row,col,dat=[],[],[]
for u,v,a,b in zip(*[iter(t[:m*4])]*4):
    for i in range(2501-a):
        row+=(i+a)*51+u,(i+a)*51+v
        col+=i*51+v,i*51+u
        dat+=b,b
for i,(c,d)in enumerate(zip(*[iter(t[m*4:])]*2),1):
    for j in range(2501-c):
        row+=j*51+i,
        col+=(j+c)*51+i,
        dat+=d,
d=csgraph.dijkstra(csr_matrix((dat,(row,col)),[8**6]*2),1,min(2500,s)*51+1)
for i in range(2,n+1):print(int(d[i::51].min()))
import math

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

print(a * b // math.gcd(a, b))


### FIXED CODE ###

# import math

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

# print(a * b // math.gcd(a, b))

def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a

def lcm(a,b):
    return a*b//gcd(a,b)

print(lcm(a,b))
H, A = input()
num = (H + (A-1))//A
print(num)

### FIXED CODE ###

H, A = input().split(" ")
H = int(H)
A = int(A)
print((H+A-1)//A)
N = int(input(""))
M = int(input(""))
ans = 0
if N == 1 :
  if M != 1 :
    ans = M * (M - 1)
else :
  if M == 1 :
    ans = N * (N - 1)
  else :
    ans = M * (M - 1) + N * (N - 1)
print(ans)


### FIXED CODE ###

num = input("")
num = num.split(" ")
N = int(num[0])
M = int(num[1])
a = int(N*(N-1)/2) if N*(N-1) >= 0 else 0
b = int(M*(M-1)/2) if M*(M-1) >= 0 else 0
print(a + b)
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, T, *AB = map(int, read().split())
    A = AB[::2]
    B = AB[1::2]

    dp = [[0] * T for _ in range(N + 1)]
    for i in range(N):
        for t in range(T):
            if 0 <= t - A[i]:
                dp[i + 1][t] = dp[i][t - A[i]] + B[i]
            if dp[i + 1][t] < dp[i][t]:
                dp[i + 1][t] = dp[i][t]

    C = [False] * N

    t = T - 1
    for i in range(N - 1, -1, -1):
        if dp[i + 1][t] == dp[i][t - A[i]] + B[i]:
            C[i] = True
            t -= A[i]

    ans = dp[N][T - 1] + max((B[i] for i in range(N) if not C[i]), default=0)

    print(ans)
    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, T, *AB = map(int, read().split())
    A = AB[::2]
    B = AB[1::2]

    dp1 = [[0] * T for _ in range(N + 1)]
    for i in range(N):
        for t in range(T):
            if 0 <= t - A[i]:
                dp1[i + 1][t] = dp1[i][t - A[i]] + B[i]
            if dp1[i + 1][t] < dp1[i][t]:
                dp1[i + 1][t] = dp1[i][t]

    dp2 = [[0] * T for _ in range(N + 1)]
    for i in range(N - 1, -1, -1):
        for t in range(T):
            if 0 <= t - A[i]:
                dp2[i][t] = dp2[i + 1][t - A[i]] + B[i]
            if dp2[i][t] < dp2[i + 1][t]:
                dp2[i][t] = dp2[i + 1][t]

    ans = 0
    for i in range(N):
        tmp = max(dp1[i][t] + dp2[i + 1][T - t - 1] for t in range(T)) + B[i]
        if ans < tmp:
            ans = tmp

    print(ans)
    return


if __name__ == '__main__':
    main()
for i in range(int(input())):
    xa, ya, xb, yb = map(int, input().split(' '))
    n = int(input())
    ip = []
    for j in range(n):
        xs, ys, xt, yt, o, l = map(int, input().split(' '))
        d = (xb - xa) * (yt - ys) - (yb - ya) * (xt - xs)
        if d == 0:
            continue
        t0 = ((yt - ys) * (xs - xa) - (xt - xs) * (ys - ya)) / d
        t1 = ((yb - ya) * (xs - xa) - (xb - xa) * (ys - ya)) / d
        if t0 < 0 or t0 > 1 or t1 < 0 or t1 > 1:
            continue
        ip.append((t0, o, l))
    ip.sort(key=lambda x: x[0])
    count = 0
    if len(ip) > 0:
        l = ip[0][2] if ip[0][1] == 1 else abs(ip[0][2] - 1)
        for p in ip[1:]:
            if p[1] == 0 and l == p[2]:
                l = abs(l - 1)
                count += 1
            elif p[1] == 1 and l != p[2]:
                l = abs(l - 1)
                count += 1
    print(count)

### FIXED CODE ###

for i in range(int(input())):
    xa, ya, xb, yb = map(int, input().split())
    n = int(input())
    ip = []
    for j in range(n):
        xs, ys, xt, yt, o, l = map(int, input().split())
        d = (xb - xa) * (yt - ys) - (yb - ya) * (xt - xs)
        if d == 0:
            continue
        t0 = ((yt - ys) * (xs - xa) - (xt - xs) * (ys - ya)) / d
        t1 = ((yb - ya) * (xs - xa) - (xb - xa) * (ys - ya)) / d
        if (t0 > 0 and t0 < 1) and (t1 > 0 and t1 < 1):
            ip.append((t0, o == l))
    count = 0
    if len(ip) > 0:
        ip.sort(key=lambda x: x[0])
        for j in range(len(ip) - 1):
            if ip[j][1] != ip[j + 1][1]:
                count += 1
    print(count)
import heapq


def dijkstra_heap(s):
    d = [float("inf")] * n
    used = [True] * n
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist, e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist, [e[0]+d[v], e[1]])
    return d


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

edge = [[] for i in range(w)]
for i in range(w):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    edge[x].append([1, y])
    edge[y].append([1, x])
d = dijkstra_heap(0)

if float('inf') in d:
    print('No')
else:
    print('Yes')
    for i, j in enumerate(d):
        if i == 0:
            continue
        print(j)


### FIXED CODE ###

import heapq


def dijkstra_heap(s):
    d = [float("inf")] * n
    prev = [float("inf")] * n
    d[s] = 0
    edgelist = [[d[s], s]]
    heapq.heapify(edgelist)

    while edgelist:
        dis, v = heapq.heappop(edgelist)
        if d[v] < dis:
            continue

        for e in edge[v]:
            if d[e] > dis + 1:
                d[e] = dis + 1
                heapq.heappush(edgelist, [dis + 1, e])
                prev[e] = v
    return d, prev


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

edge = [[] for i in range(n)]
for i in range(w):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    edge[x].append(y)
    edge[y].append(x)
d, prev = dijkstra_heap(0)

if float('inf') in prev[1:]:
    print('No')
else:
    print('Yes')
    for i in prev[1:]:
        print(i + 1)
#ls = list(input())
ls = [*input()]
flg = False
for i in range(len(ls)-1):
    if ls[i] == ls[i+1]:
        flg=True

if (flg): 
    print('Bad') 
else: 
    print('Good')

### FIXED CODE ###

ls = list(input())
flg = False
for i in range(len(ls)-1):
    if ls[i] == ls[i+1]:
        flg=True

if (flg): 
    print('Bad') 
else: 
    print('Good')
n = int(input())
L = list(map(int,input().split()))
S = []
for i in range(n):
  S.append([L[i],i+1])
S.sort()
for i in range(n):
  print(' '.join(S[i][1]))

### FIXED CODE ###

n = int(input())
L = list(map(int,input().split()))
S = []
K = []
for i in range(n):
  S.append([L[i],i+1])
S.sort()
for i in range(n):
  K.append(S[i][1])
print(' '.join(map(str,K)))
a=input().split('/')
a=a[0]+a[1]+a[2]
if int(a) > 2019430
  print("TDB")
else
  print('Heisei')

### FIXED CODE ###

a=input().split('/')
a=a[0]+a[1]+a[2]
if int(a) > 20190430:
  print("TBD")
else:
  print('Heisei')