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

from collections import deque
from heapq import *

n,m,s,t=map(int,input().split())
s-=1
t-=1
INF=10**19
Gyen=[[]for i in range(n)]
Gsnu=[[]for i in range(n)]
for i in range(m):
  u,v,a,b=map(int,input().split())
  u-=1
  v-=1
  Gyen[u].append([v,a])
  Gyen[v].append([u,a])
  Gsnu[u].append([v,b])
  Gsnu[v].append([u,b])

def dijkstra(G,s):
  que=[]
  d=[INF]*n
  d[s]=0
  visited={s}
  heappush(que,[0,s])
  while(que):
    p=heappop(que)
    v=p[1]
    visited.add(v)
    if d[v]<p[0]:
      continue
    for node,cost in G[v]:
      if (node not in visited) and d[node]>d[v]+cost:
        d[node]=d[v]+cost
        heappush(que,[d[node],node])
  return d

yen=dijkstra(Gyen,s)
snu=dijkstra(Gsnu,t)
l=[INF]
for i in range(n-1,-1,-1) :
  l.append(min(l[-1],yen[i]+snu[i]))
for i in l[n:0:-1]:
  print(10**15-i)


### FIXED CODE ###

from heapq import *

n,m,s,t=map(int,input().split())
s-=1
t-=1
INF=10**19
Gyen=[[]for i in range(n)]
Gsnu=[[]for i in range(n)]
for i in range(m):
  u,v,a,b=map(int,input().split())
  u-=1
  v-=1
  Gyen[u].append([v,a])
  Gyen[v].append([u,a])
  Gsnu[u].append([v,b])
  Gsnu[v].append([u,b])

def dijkstra(G,s):
  que=[]
  d=[INF]*n
  d[s]=0
  visited={s}
  heappush(que,[0,s])
  while(que):
    p=heappop(que)
    v=p[1]
    visited.add(v)
    for node,cost in G[v]:
      if (node not in visited) and d[node]>d[v]+cost:
        d[node]=d[v]+cost
        heappush(que,[d[node],node])
  return d

yen=dijkstra(Gyen,s)
snu=dijkstra(Gsnu,t)
ans=10**15
ans_list=[]
for i in reversed(range(n)):
  ans=min(ans,yen[i]+snu[i])
  ans_list.append(10**15-ans)
print(*ans_list[::-1], sep='\n')
### BUGGY CODE ###

import itertools
S = input()
l = len(S)
nums = range(1, l+1)
ans = 0
for i in itertools.combinations_with_replacement(nums, 2):
    # print(i[0])
    n = int(S[i[0]-1:i[1]])
    if n % 2019 == 0:
        ans += 1

print(ans)


### FIXED CODE ###

# import itertools
S = input()[::-1]
# l = len(S)
# nums = range(1, l+1)
count = [0]*2019
count[0] = 1
num = 0
d = 1
for i in S:
    num += int(i)*d
    count[num % 2019] += 1
    d *= 10
    d %= 2019

ans = 0
for i in count:
    ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

import math

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

m = -1
c = 0
for x in range(0,min(b,n)+1):
    c = math.floor(a*x/b)-a*math.floor(x/b)
    #print('a:',c)
    if c >= m:
        m=c
    else:
        break
if n>b:
    for x in range(b,n+1,b):
        c = math.floor(a*x/b)-a*math.floor(x/b)
        #print('b:',c)
        if c >= m:
            m=c
        else:
            break
print(m)

### FIXED CODE ###

import math

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

m = 0
if n<b:
    m = math.floor(a*n/b)
else:
    m = math.floor(a*(b-1)/b)-a*math.floor((b-1)/b)
print(m)
### BUGGY CODE ###

import math
import random
from operator import itemgetter
import re
import sys
from itertools import accumulate
from collections import defaultdict
from collections import deque
from bisect import bisect_left,bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import functools
N = int(input())
x = [int(i) for i in input().split()]
mod = 10**9+7
start = 1
all_dis = 0
for i in range(N-1):
    far = x[i+1]-x[i]
    all_dis += far*start*math.factorial(N-1)//math.factorial(i+1)
    start = (start*(i+2)+math.factorial(i+1))%mod
    all_dis %= mod
print(all_dis)

### FIXED CODE ###

import math
import random
from operator import itemgetter
import re
import sys
from itertools import accumulate
from collections import defaultdict
from collections import deque
from bisect import bisect_left,bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import functools
N = int(input())
x = [int(i) for i in input().split()]
mod = 10**9+7
start = 1
st = 1
st_list = [0] * N
st_rev = [0] * N
for i in range(N-1):
    st *= (i+1)
    st %= mod
    st_list[i] = st
    st_rev[i] = pow(st,mod-2,mod)
all_dis = 0
for i in range(N-1):
    far = x[i+1]-x[i]
    all_dis += far*start*st_list[N-2]*st_rev[i]
    start = (start*(i+2)+st_list[i])%mod
    all_dis %= mod
print(all_dis)
### BUGGY CODE ###

import numpy as np

left_max = -1
right_max = -1
right_max_index = 0

N = int(input())
A_list = [int(input()) for _ in range(N)]
np_A_list = np.array(A_list)
for i, A in enumerate(A_list):
    # 右端
    if i == len(A_list) - 1:
        print(left_max)
        break
    if right_max_index == i:
        slc = np_A_list[i + 1:]
        right_max = slc.max()
        right_max_index = slc.argmax() + i + 1

    if left_max > right_max:
        print(left_max)
    else:
        print(right_max)
    
    if left_max < A:
        left_max = A


### FIXED CODE ###

import numpy as np

now_max = -1
prev_max = 100000000
left_max = -1
right_max = -1
right_max_index = 0

N = int(input())
A_list = [int(input()) for _ in range(N)]
np_A_list = np.array(A_list)
for i, A in enumerate(A_list):
    # 右端
    if i == len(A_list) - 1:
        print(left_max)
        break
    if right_max_index == i:
        slc = np_A_list[i + 1:]
        right_max = slc.max()
        right_max_index = len(np_A_list) - 1 - slc[::-1].argmax()

    if left_max > right_max:
        now_max = left_max
        print(left_max)
    else:
        now_max = right_max
        print(right_max)
    
    if prev_max < now_max:
        left_max = right_max = now_max
        right_max_index = 10000000
    
    prev_max = now_max
    if left_max < A:
        left_max = A
### BUGGY CODE ###

s = input()
lst = []
for i in range(len(s)):
  n = int(s[i::])
  lst.append(n%2019)
lst.append(0)
lst.sort()
counter = 1
stock = lst[0]
ans = 0
for i in range(1, len(lst)):
  if stock == lst[i]:
    counter += 1
  else:
    ans += counter*(counter - 1)//2
    counter = 1
    stock = lst[i]
if counter >= 2:
  ans += counter*(counter - 1)//2
print(ans)

### FIXED CODE ###

import collections
MOD = 2019

def mod(n):         
  return n % MOD

def modpow(a, n):   #mod(a**n)を高速で求める
    res = 1  
    digit = len(str(bin(n))) - 2
    for i in range(digit):
      if (n >> i) & 1:
        res *= mod(a)
        res = mod(res)
      a = mod(a**2)
    return mod(res)

s = input()
lst = []
n = 0
for i in range(len(s)):
  n += mod(int(s[len(s)-i-1])*modpow(10, i))
  lst.append(mod(n))
lst.append(0)
lst.sort()
ans = 0
counter = 1
stock = lst[0]
for i in range(1, len(lst)):
  if stock == lst[i]:
    counter += 1
  else:
    ans += counter*(counter - 1)//2
    counter = 1
    stock = lst[i]
if counter >= 2:
  ans += counter*(counter - 1)//2
print(ans)
### BUGGY CODE ###

n, m = (int(_) for _ in input().split())
ab_list = [[int(i) for i in input().split()] for i in range(n)]
a_list = []
b_list = []
for i in range(n):
    a_list.append(ab_list[i][0])
    b_list.append(ab_list[i][1])


buy = 0
money = 0
while (n >= 0):
    min_a = min(a_list)
    min_index = a_list.index(min_a)
    if (buy + b_list[min_index] < m):
        money += b_list[min_index] * a_list[min_index]
        buy += b_list[min_index]
    else:
        money += (m - buy) * a_list[min_index]
        break

    a_list.pop(min_index)
    b_list.pop(min_index)

    n -= 1

print(money)


### FIXED CODE ###

n, m = (int(_) for _ in input().split())
ab_list = [[int(i) for i in input().split()] for i in range(n)]

ab_list = sorted(ab_list)

buy = 0
money = 0
j = 0


while (buy < m):
    buy += ab_list[j][1]
    money += ab_list[j][0] * ab_list[j][1]
    j += 1

print(money-(ab_list[j-1][0]*(buy-m)))
### BUGGY CODE ###

import collections
import math
import copy

H,W=map(int,input().split())

A=[list(str(input())) for i in range(H)]
#1<=sy<=R
d=[[-1 for j in range(W)]for i in range(H)]
inf=10**6
ans=0
queue=collections.deque()
for i in range(H):
    for j in range(W):
        if A[i][j]=='#':
            queue.append([i,j])
            d[i][j]=0

moves=[[1,0],[-1,0],[0,1],[0,-1]]

nax=0
while len(queue)>0:
    now=queue.popleft()
    for i in range(4):
        ny=now[0]+moves[i][0]
        nx=now[1]+moves[i][1]
        if 0<=ny and ny<H and 0<=nx and nx<W and A[ny][nx]=='.' and d[ny][nx]==-1:
            d[ny][nx]=d[now[0]][now[1]]+1
            nax=max(nax,d[ny][nx])
            queue.append([ny,nx])


print(nax)

### FIXED CODE ###

import collections
import math
import copy

H,W=map(int,input().split())

A=[list(str(input())) for i in range(H)]
#1<=sy<=R
d=[[-1 for j in range(W)]for i in range(H)]
inf=10**6
ans=0
queue=collections.deque()
for i in range(H):
    for j in range(W):
        if A[i][j]=='#':
            queue.append([i,j])
            d[i][j]=0

moves=[[1,0],[-1,0],[0,1],[0,-1]]

nax=0
while len(queue)>0:
    now=queue.popleft()
    for i in range(4):
        ny=now[0]+moves[i][0]
        nx=now[1]+moves[i][1]
        if 0<=ny and ny<H and 0<=nx and nx<W and A[ny][nx]=='.' and d[ny][nx]==-1:
            d[ny][nx]=d[now[0]][now[1]]+1
            nax=max(nax,d[ny][nx])
            queue.append([ny,nx])


print(nax)
### BUGGY CODE ###

import sys

def is_ok(mid, gen=None, diff=0):
    print(mid, flush=True)
    res = input()
    if res == "Vacant":
        sys.exit()
    if gen is None:
        return res
    if diff % 2 == 0:
        return gen == res
    else:
        return gen != res


def meguru_bisect_kai(ng, ok, gen):
    cnt = 0
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if is_ok(mid, gen, ok - mid):
            ok = mid
        else:
            ng = mid
    return ok


n = int(input())
gen = is_ok(n - 1)
meguru_bisect_kai(0, n - 1, gen)

### FIXED CODE ###

n = int(input())

print(0, flush=True)
res = input()
if res == "Vacant":
    exit()

left = 0
right = n
gen = res


while True:
    mid = (left + right) // 2
    print(mid, flush=True)
    res = input()

    if res == "Vacant":
        exit()

    if gen == res:
        if (mid - left) % 2:
            right = mid
        else:
            left = mid
    else:
        if (mid - left) % 2:
            left = mid
            gen = res
        else:
            right = mid
### BUGGY CODE ###

S = input()
mod = 10**9 + 7
dp = [[0] * 13 for i in range(len(S)+1)]  # the number of ways to make a number with remainder j using the first i digits
dp[0][0] = 1
for i in range(len(S)):

    if S[i] == '?':
        for d in range(10):
            for j in range(13):
                dp[i+1][(j * 10 + d) % 13] += dp[i][j]
                dp[i+1][(j * 10 + d) % 13] %= mod
    else:
        d = int(S[i])
        for j in range(13):
            dp[i+1][(j * 10 + d) % 13] += dp[i][j]
print(dp[len(S)][5])


### FIXED CODE ###

import numpy as np
 
s = input()
p = np.array([0]*13)
p[0] = 1
 
amari = [[0]*13 for _ in range(13)]
for j in range(10):
  for i in range(13):
    amari[i][(i*10+j)%13] += 1
M = np.array(amari)
 
for si in range(len(s)):
  a = np.array([0]*13)
  if s[si] == '?':
    a = np.dot(p,M)
  else:
    c = int(s[si])
    for i in range(13):
      a[(i*10+c)%13] += p[i]
  p = np.mod(a,1000000007)
print(p[5])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
class mint(object):
    MOD=998244353

    def __init__(self,x):
        self.__x=x%self.MOD

    def __repr__(self):
        return str(self.__x)

    def __add__(self,other):
        return mint(self.__x+other.__x) if isinstance(other,mint) else mint(self.__x+other)

    def __sub__(self,other):
        return mint(self.__x-other.__x) if isinstance(other,mint) else mint(self.__x-other)

    def __mul__(self,other):
        return mint(self.__x*other.__x) if isinstance(other,mint) else mint(self.__x*other)

    def __truediv__(self,other):
        return mint(self.__x*pow(other.__x,self.MOD-2,self.MOD)) if isinstance(other, mint) else mint(self.__x*pow(other, self.MOD-2,self.MOD))

    def __pow__(self,other):
        return mint(pow(self.__x,other.__x,self.MOD)) if isinstance(other,mint) else mint(pow(self.__x,other,self.MOD))

    __radd__=__add__

    def __rsub__(self,other):
        return mint(other.__x-self.__x) if isinstance(other,mint) else mint(other-self.__x)

    __rmul__=__mul__

    def __rtruediv__(self,other):
        return mint(other.__x*pow(self.__x,self.MOD-2,self.MOD)) if isinstance(other,mint) else mint(other*pow(self.__x,self.MOD-2,self.MOD))

    def __rpow__(self,other):
        return mint(pow(other.__x,self.__x,self.MOD)) if isinstance(other,mint) else mint(pow(other,self.__x,self.MOD))

def resolve():
    # preparation
    p=int(input())
    mint.MOD=p
    invfact=[0]*p
    invfact[p-1]=mint(-1) # Wilson's theorem
    for i in range(2,p):
        invfact[p-i]=invfact[p-i+1]*(p-i+1)

    # initialize
    A=[0]*p
    for i,a in enumerate(map(int,input().split())):
        A[i]=mint(a)

    ans=[mint(0)]*p
    ans[0]=A[0]
    r=[mint(0)]*(p+1) # for use of r[-1]=0
    r[0]=mint(1)

    # iterate
    for k in range(1,p):
        newr=[0]*(p+1) # newr(x)=(x-(k-1))r(x)
        v=0 # v=f[k-1](k)
        power=1
        for i in range(p):
            v+=ans[i]*power
            power*=k
            newr[i]=r[i-1]-(k-1)*r[i]
        r=newr
        for i in range(p):
            ans[i]+=(A[k]-v)*invfact[k]*r[i]

    print(*ans)
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    # preparation
    p=int(input())
    invfact=[0]*p
    invfact[p-1]=p-1 # Wilson's theorem
    for i in range(2,p):
        invfact[p-i]=invfact[p-i+1]*(p-i+1)%p

    # initialize
    A=list(map(int,input().split()))
    ans=[0]*p
    ans[0]=A[0]
    r=[0]*(p+1) # for use of r[-1]=0
    r[0]=1

    # iterate
    for k in range(1,p):
        newr=[0]*(p+1) # newr(x)=(x-(k-1))r(x)
        v=0 # v=f[k-1](k)
        power=1
        for i in range(p):
            v+=ans[i]*power%p
            power*=k
            power%=p
            newr[i]=(r[i-1]-(k-1)*r[i])%p
        r=newr
        for i in range(p):
            ans[i]+=(A[k]-v)*invfact[k]*r[i]
            ans[i]%=p
    print(*ans)
resolve()
### BUGGY CODE ###

n=int(input())
D=[int(i) for i in input().split()]
if n>=24:
  print(0)
else:
  ans=0
  for i in range(2**(n-1)):
    C=[0,D[0],24]
    for j in range(n-1):
      if i&(1<<j):
        C.append(24-D[j+1])
      else:
        C.append(D[j+1])
    C.sort()
    cur=24
    for j in range(n+1):
      cur=min(cur,C[j+1]-C[j])
    ans=max(ans,cur)
  print(ans)

### FIXED CODE ###

n=int(input())
D=[int(i) for i in input().split()]
C=[1]+[0]*12

for d in D:
  C[min(d,24-d)]+=1
if max(C)>2 or C[0]>1 or C[12]>1:
  print(0)
else:
  ans=0
  
  for i in range(2**(11)):
    CC=[1]+[0]*23+[1]
    for j in range(1,12):
      if C[j]==2:
        CC[j]=1
        CC[24-j]=1
      elif C[j]==1:
        if i&(1<<(j-1)):
          CC[j]=1
        else:
          CC[24-j]=1
    if C[12]==1:
      CC[12]=1
    cur=24
    t=0
    for j in range(1,25):
      if CC[j]==1:
        cur=min(cur,t+1)
        t=0
      else:
        t+=1
    ans=max(ans,cur)
  print(ans)
### BUGGY CODE ###

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

smap = [list(input()) for _ in range(h)]
cmap = [[float('inf') for _ in range(w)] for _ in range(h)]
queue = [(0,0)]
l = [(1,0), (-1,0), (0,1), (0,-1)]

initial_whites = 0

for x in smap:
    for y in x:
        if y == '.':
            initial_whites += 1

cmap[0][0] = 0

while queue:
    v = queue.pop(0)
    smap[v[0]][v[1]] = '#'
    for x in l:
        y = (v[0]+x[0], v[1]+x[1])
        if 0 <= y[0] <= h-1 and 0 <= y[1] <= w-1:
            if smap[y[0]][y[1]] == '.':
                cmap[y[0]][y[1]] = cmap[v[0]][v[1]] + 1
                queue.append(y)
            else:
                pass
        else:
            pass


if cmap[h-1][w-1] == float('inf'):
    print(-1)
else:
    print(initial_whites - cmap[h-1][w-1] - 1)

### FIXED CODE ###

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

smap = []
for _ in range(h):
    s = input()
    ss = []
    for i in range(w):
        ss.append(s[i])
    smap.append(ss)
cmap = [[float('inf') for _ in range(w)] for _ in range(h)]
queue = [(0,0)]
l = [(1,0), (-1,0), (0,1), (0,-1)]

initial_whites = 0

for x in smap:
    for y in x:
        if y == '.':
            initial_whites += 1

cmap[0][0] = 0

while queue:
    v = queue.pop(0)
    smap[v[0]][v[1]] = '#'
    for x in l:
        y = (v[0]+x[0], v[1]+x[1])
        if 0 <= y[0] <= h-1 and 0 <= y[1] <= w-1:
            if smap[y[0]][y[1]] == '.':
                smap[y[0]][y[1]] = '#'
                cmap[y[0]][y[1]] = cmap[v[0]][v[1]] + 1
                queue.append(y)
            else:
                pass
        else:
            pass


if cmap[h-1][w-1] == float('inf'):
    print(-1)
else:
    print(initial_whites - cmap[h-1][w-1] - 1)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(100000)


def check(i, xs):
    xi = xs[i]
    children = set()
    for j, d in links[i]:
        if j in checked:
            continue
        xj = xs[j]
        if xj is None:
            xs[j] = xi + d
        elif xi + d != xj:
            return False
        children.add(j)
    checked.add(i)
    for jc in children:
        if not check(jc, xs):
            return False
    return True


def solve():
    for i in range(n):
        if i not in checked:
            xs = [None] * n
            xs[i] = 0
            res = check(i, xs)
            if not res:
                return False
            xf = [x for x in xs if x is not None]
            mn, mx = min(xf), max(xf)
            if mx - mn > 1e9:
                return False
    return True


n, m = map(int, input().split())
links = [set() for _ in range(n)]
for _ in range(m):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    links[l].add((r, d))
    links[r].add((l, -d))
checked = set()
print('Yes' if solve() else 'No')


### FIXED CODE ###

import sys

sys.setrecursionlimit(100000)


def check(i, xs, checked):
    xi = xs[i]
    children = set()
    for j, d in links[i]:
        if checked[j]:
            continue
        if j not in xs:
            xs[j] = xi + d
        elif xi + d != xs[j]:
            return False
        children.add(j)
    checked[i] = True
    for j in children:
        if not check(j, xs, checked):
            return False
    return True


def solve():
    checked = [False] * n
    for i in range(n):
        if not checked[i]:
            xs = {}
            xs[i] = 0
            res = check(i, xs, checked)
            if not res:
                return False
            mn, mx = min(xs.values()), max(xs.values())
            if mx - mn > 1e9:
                return False
    return True


n, m = map(int, input().split())
links = [set() for _ in range(n)]
for _ in range(m):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    links[l].add((r, d))
    links[r].add((l, -d))
print('Yes' if solve() else 'No')
### BUGGY CODE ###

from fractions import gcd

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

lst = [0]*(max(As)+1)

for a in As:
  i = 2
  if a % i == 0:
    lst[i] += 1
  while a % i == 0:
    a //= i
  i = 3
  while i**2 <= N:
    if a % i == 0:
      lst[i] += 1  
    while a % i == 0:
      a //= i
    i += 2
  if a > 1:
    lst[a] += 1
    
if max(lst) < 2:
  print('pairwise coprime')
  exit()
  
t = As[0]

for a in As:
  t = gcd(t,a)
  
if t == 1:
  print('setwise coprime')
else:
  print('not coprime')


### FIXED CODE ###

from fractions import gcd

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

A = max(As)
lst = [0]*(A+1)
rlt = [0]*(A+1)

for i in range(2, A+1):
  if lst[i] > 0:
    continue
  j = 1
  while i*j <= A:
    if lst[i*j] == 0:
      lst[i*j] = i
    j += 1
  if j == 1:
    break
    
for a in As:
  tmp = -1
  while a > 1:
    if tmp != lst[a]:
      rlt[lst[a]] += 1
      tmp = lst[a]
    a //= lst[a]

r = max(rlt) 

if r < 2:
  print('pairwise coprime')
elif r < N:
  print('setwise coprime')
else:
  print('not coprime')
### BUGGY CODE ###

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

sumA = [0]*(N+1)

for i in range(N):
    sumA[i+1] = sumA[i]+A[i]
ans = 0
for i in range(1, N+1):
    for j in range(0, i):
        if sumA[i] - sumA[j] == 0:
            ans += 1

print(ans)


### FIXED CODE ###

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

sumA = [0]*(N+1)
table = collections.defaultdict(int)
table[0] += 1
for i in range(N):
    sumA[i+1] = sumA[i]+A[i]
    table[sumA[i+1]] += 1
ans = 0
table = table.values()
table = [x for x in table if x > 1]
for x in table:
    ans += x*(x-1)//2

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


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

for i in range(n):
    print(a.count(i+1))



### FIXED CODE ###

import sys

n = int(input())
a = list(map(int, input().split()))
b = [0 for _ in range(n)]


asize = len(a)
for i in range(asize):
    b[a[i]-1] += 1

for i in range(n):
    print(b[i])
### BUGGY CODE ###

n = int(input())
t = []
m = 0

for i in range(n):
    s = list(input())
    s.sort()
    t.append(s)
    
t.sort()

for i in range(n):
    for j in range(n - i - 1):
        if t[i] == t[i + j + 1]:
            m += 1
        else:
            break
        
print(m)
    

### FIXED CODE ###

n = int(input())
d = {}
ans = 0
for _ in range(n):
    s = list(input())
    s.sort()
    s = "".join(s)
    if s in d:
        d[s] += 1
        ans += d[s]
    else:
        d.update({s : 0})
print(ans)
### BUGGY CODE ###

from  collections import deque
N,M,K=list(map(int,input().split()))
AB=[list(map(int,input().split())) for i in range(M)]
CD=[list(map(int,input().split())) for i in range(K)]

user=[0 for i in range(N+1)]
graph_ab=[[] for i in range(N+1)]
graph_cd=[[] for i in range(N+1)]
for i in range(M):
    a,b=AB[i]
    graph_ab[a].append(b)
    graph_ab[b].append(a)
for i in range(K):
    c,d=CD[i]
    graph_cd[c].append(d)
    graph_cd[d].append(c)
    
for j in range(1,N+1):
    stack=deque([j])
    visited=[-1 for i in range(N+1)]
    visited[j]=0
    while stack:
        x=stack.popleft()
        for i in graph_ab[x]:
            if visited[i]<0:
                visited[i]=1
                stack.append(i)
                
    for i in range(1,N+1):
        if visited[i]==1 and (i not in graph_ab[j]) and (i not in graph_cd[j]):
            user[j]+=1
del user[0]
print(*user)

### FIXED CODE ###

from  collections import deque,Counter
N,M,K=list(map(int,input().split()))
AB=[list(map(int,input().split())) for i in range(M)]
CD=[list(map(int,input().split())) for i in range(K)]

user=[0 for i in range(N+1)]
graph_ab=[[] for i in range(N+1)]
graph_cd=[[] for i in range(N+1)]
visited=[0 for i in range(N+1)]
for i in range(M):
    a,b=AB[i]
    graph_ab[a].append(b)
    graph_ab[b].append(a)
time=0
for j in range(1,N+1):
    if visited[j]==0:
        stack=deque([j])
        time+=1
        visited[j]=time
        while stack:
            x=stack.popleft()
            for i in graph_ab[x]:
                if visited[i]==0:
                    visited[i]=time
                    stack.append(i)
#     visit_list[j]=visited
counter=Counter(visited) 
for i in range(K):
    c,d=CD[i]
    if visited[c]==visited[d]:
        graph_cd[c].append(d)
        graph_cd[d].append(c)

for i in range(1,N+1):
    user[i]=counter[visited[i]]-len(graph_ab[i])-len(graph_cd[i])-1

del user[0]
print(*user)