Consider a football tournament where n teams participate. Each team has two football kits: for home games, and for away games. The kit for home games of the i-th team has color x_{i} and the kit for away games of this team has color y_{i} (x_{i} ≠ y_{i}).

In the tournament, each team plays exactly one home game and exactly one away game with each other team (n(n - 1) games in total). The team, that plays the home game, traditionally plays in its home kit. The team that plays an away game plays in its away kit. However, if two teams has the kits of the same color, they cannot be distinguished. In this case the away team plays in its home kit.

Calculate how many games in the described tournament each team plays in its home kit and how many games it plays in its away kit.


-----Input-----

The first line contains a single integer n (2 ≤ n ≤ 10^5) — the number of teams. Next n lines contain the description of the teams. The i-th line contains two space-separated numbers x_{i}, y_{i} (1 ≤ x_{i}, y_{i} ≤ 10^5; x_{i} ≠ y_{i}) — the color numbers for the home and away kits of the i-th team.


-----Output-----

For each team, print on a single line two space-separated integers — the number of games this team is going to play in home and away kits, correspondingly. Print the answers for the teams in the order they appeared in the input.


-----Examples-----
Input
2
1 2
2 1

Output
2 0
2 0

Input
3
1 2
2 1
1 3

Output
3 1
4 0
2 2

Difficulty: interview

Starter code:

Solutions:
def main():
    n = int(input())
    teams = [input().split() for _ in range(n)]
    ans = [list((0, 0)) for _ in range(n)]
    home = dict()

    for i in range(n):
        home[teams[i][0]] = home.get(teams[i][0], 0) + 1

    for i in range(n):
        ans[i][0] = n - 1 + home.get(teams[i][1], 0)
        ans[i][1] = n - 1 - home.get(teams[i][1], 0)

    for i in range(n):
        ans[i] = '{} {}'.format(ans[i][0], ans[i][1])

    print('\n'.join(ans))

def __starting_point():
    main()
__starting_point()

import sys

f = sys.stdin
n = int(f.readline().strip())

A = []
F = {}
for k in range(n):
    t = list(map(int, f.readline().strip().split()))
    A.append(t)
    if t[0] in F:
        F[t[0]] += 1
    else :
        F[t[0]] = 1

res = ''
p = []
for u in A:

    if u[1] in F:
       p.append(str(n-1+F[u[1]])+' '+str(n-1-F[u[1]]))
    else:
       p.append(str(n-1)+' '+str(n-1)) 

print('\n'.join(p))


n = int(input())
a = []
b = [0] * 100001
for i in range(n):
  x, y = map(int, input().split())
  a += [y]
  b[x] += 1
print("\n".join("{} {}".format(n - 1 + b[y], n - 1 - b[y]) for y in a))

n = int(input())
a = [0] * 10 ** 6
b = []
for i in range(n):
    q, w = map(int, input().split())
    a[q] += 1
    b.append(w)
for i in range(n):
    print(n - 1 + a[b[i]], n - 1 - a[b[i]])

def main():
    n = int(input())
    teams = [input().split() for _ in range(n)]
    ans = [list((0, 0)) for _ in range(n)]
    home = dict()

    for i in range(n):
        home[teams[i][0]] = home.get(teams[i][0], 0) + 1

    for i in range(n):
        ans[i][0] = n - 1 + home.get(teams[i][1], 0)
        ans[i][1] = n - 1 - home.get(teams[i][1], 0)

    for i in range(n):
        ans[i] = '{} {}'.format(ans[i][0], ans[i][1])

    print('\n'.join(ans))

def __starting_point():
    main()
__starting_point()

def main():
    n = int(input())
    teams = [input().split() for _ in range(n)]
    ans = [[0, 0] for _ in range(n)]
    home = dict()

    for i in range(n):
        home[teams[i][0]] = home.get(teams[i][0], 0) + 1

    for i in range(n):
        ans[i][0] = n - 1 + home.get(teams[i][1], 0)
        ans[i][1] = n - 1 - home.get(teams[i][1], 0)

    for i in range(n):
        ans[i] = '{} {}'.format(ans[i][0], ans[i][1])

    print('\n'.join(ans))

def __starting_point():
    main()
__starting_point()

def main():
    n = int(input())
    teams = [list(map(int, input().split())) for _ in range(n)]
    ans = [[n - 1, 0] for _ in range(n)]
    home = [0] * ((10 ** 5) + 1)

    for i in range(n):
        home[teams[i][0]] += 1

    for i in range(n):
        ans[i][0] += home[teams[i][1]]
        ans[i][1] = n - 1 - home[teams[i][1]]

    for i in range(n):
        ans[i] = '{} {}'.format(ans[i][0], ans[i][1])

    print('\n'.join(ans))

def __starting_point():
    main()
__starting_point()

n = int(input())
teams = [list(map(int, input().split())) for _ in range(n)]
ans = [[n - 1, 0] for _ in range(n)]
home = [0] * ((10 ** 5) + 1)

for i in range(n):
    home[teams[i][0]] += 1

for i in range(n):
    ans[i][0] += home[teams[i][1]]
    ans[i][1] = n - 1 - home[teams[i][1]]

for i in range(n):
    ans[i] = '{} {}'.format(ans[i][0], ans[i][1])

print('\n'.join(ans))

def main():
    n = int(input())
    teams = [list(map(int, input().split())) for _ in range(n)]
    home = [0] * ((10 ** 5) + 1)
    ans = list()

    for i in range(n):
        home[teams[i][0]] += 1

    print('\n'.join('{} {}'.format(n - 1 + home[teams[i][1]], n - 1 - home[teams[i][1]]) for i in range(n)))

def __starting_point():
    main()
__starting_point()

def main():
    n = int(input())
    teams = [input().split() for _ in range(n)]
    home = dict()
    ans = list()

    for i in range(n):
        home[teams[i][0]] = home.get(teams[i][0], 0) + 1

    print('\n'.join('{} {}'.format(n - 1 + home.get(teams[i][1], 0),
            n - 1 - home.get(teams[i][1], 0)) for i in range(n)))

def __starting_point():
    main()
__starting_point()

__author__ = 'Lipen'

def main():
	n = int(input())
	X = []
	Y = []
	color = [0]*100001

	for i in range(n):
		x,y = map(int, input().split())
		X.append(x)
		Y.append(y)
		color[x] += 1

	s = ''
	for i in range(n):
		z = color[Y[i]]
		s += '{} {}\n'.format(n-1+z, n-1-z)
	print(s[:-1])

main()

n = int(input())
c = [0] * 100001
y = [0] * n
for i in range(n):
    x, y[i] = list(map(int, input().split()))
    c[x]+=1

for i in range(n):
    a = n - 1 + c[y[i]]
    b = 2 * n - 2 - a
    print(a, b)



n = int(input())
a = [0 for i in range(n)]
x = [0 for i in range(100001)]
for i in range(n):
    s, a[i] = map(int, input().split())
    x[s] += 1
for i in range(n):
    print(n - 1 + x[a[i]], n - 1 - x[a[i]])

def ret(n):
    if n in col:
        return(col[n])
    else:
        return(0)
n = int(input())
col = {}
t = []
for i in range(n):
    a = input().split()
    t.append([n-1,a[1]])
    if a[0] not in col:
        col[a[0]] = 1
    else:
        col[a[0]] += 1

print('\n'.join('%d %d' % (x[0] + ret(x[1]), (n-1) - ret(x[1])) for x in t))


n = int(input())
u, v = [0] * n, [0] * 100001
for i in range(n):
    x, y = map(int, input().split())
    u[i] = y
    v[x] += 1
for i in range(n):
    k = v[u[i]]
    u[i] = str(n - 1 + k) + ' ' + str(n - 1 - k)
print('\n'.join(u))

n = int( input() )
x, y = [0] * n, [0] * n
for i in range( n ):
    x[i], y[i] = map( int, input().split() )
ans = [0] * 100001
for elm in x:
    ans[elm] += 1
for elm in y:
    print( n - 1 + ans[elm], n - 1 - ans[elm] )

n = int(input())

local = [0]*(10**5+1)

kits = []

for i in range(n):
    x, y = list(map(int, input().split(" ")))
    kits.append((x, y))
    local[x] += 1

res = ["%s %s" % (n-1+local[y], n-1-local[y]) for (x, y) in kits]

print("\n".join(res))

n = int(input())
home = {}
guest = []

for i in range(n):
    h, g = [int(c) for c in input().split()]
    home[h] = 1 if not(h in home) else home[h] + 1
    guest.append(g)

for i in range(n):
    h = (n - 1) + (0 if not(guest[i] in home) else home[guest[i]])
    print('%s %s' % (h, ((n - 1) * 2) - h))


import sys


def main():
    line_num = 0
    teams_num = 0
    teams_per_color = {}
    teams = []
    # read input data
    for line in sys.stdin:
        if line_num == 0:
            teams_num = int(line.strip())
        elif line_num <= teams_num:
            res = list([int(x) for x in line.strip().split(' ')])
            if res[0] not in teams_per_color:
                teams_per_color[res[0]] = 0
            teams_per_color[res[0]] = teams_per_color[res[0]] + 1
            teams.append((res[0], res[1]))
        line_num += 1
        if line_num > teams_num:
            break
    # - if 1 color belongs to 1 team only -> there will be no problems with this
    # team and this team will wear this color during all games of one type.
    # - if all teams that wear this color have one kit_type (all play away
    # games in this color, for example, then there will be no problems, as
    # we don't have away-away team problem)
    # - otherwise have to calculate 'delta': times when need to change AWAY
    # kit to HOME one
    for i in range(0, teams_num):
        # if away color is shared among some home-teams, then have to change
        away_color = teams[i][1]
        result = (teams_num - 1 + teams_per_color.get(away_color, 0),
                  teams_num - 1 - teams_per_color.get(away_color, 0))
        print("{} {}".format(result[0], result[1]))

def __starting_point():
    main()

__starting_point()

n = int(input())
nbColors = [0 for i in range(10**5 + 1)]
teamAway = []
for i in range(n):
	home, away = map(int, input().split())
	nbColors[home] += 1
	teamAway.append(away)

for away in teamAway:
	print(n - 1 + nbColors[away], n - 1 - nbColors[away])

n = int(input())
i = 0
l1 = list()
l2 = list()
l3 = [0] + [0] * 10**5
l4 = [0] + [0] * 10**5
i = 0
while i < n:
    x, y = list(map(int,input().split()))
    l1.append(x)
    l2.append(y)
    l3[x] += 1
    l4[y] += 1
    i += 1

i = 0
for i in range(n):
    print(n-1 + l3[l2[i]], n-1 - l3[l2[i]])
    


n = int(input())
a = [0]*n
x = [0]*100001

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

for i in range(n):
    print(n-1+x[a[i]], n-1-x[a[i]])


n,i,o = int(input()),[0 for z in range(10**5+1)],[]
for k in range(n):
    inp1,inp2 = list(map(int,input().split()))
    i[inp1]+=1; o.append(inp2)
for k in o: print(n-1+i[k], n-1-i[k])

import sys
import math

n = int(sys.stdin.readline())

a = [0] * 100000
b = [0] * 100000

d = []
for i in range(n):
    h, g = [int(x) for x in (sys.stdin.readline()).split()]
    d.append((h - 1, g - 1))
    a[h - 1] += 1
    b[g - 1] += 1
   
for i in d:
    print(str((n - 1) + (a[i[1]])) + " " + str(n - a[i[1]] - 1))

import sys
import math

n = int(sys.stdin.readline())

a = [0] * 100000

d = []
for i in range(n):
    h, g = [int(x) for x in (sys.stdin.readline()).split()]
    d.append(g - 1)
    a[h - 1] += 1
   
for i in d:
    print(str((n - 1) + (a[i])) + " " + str(n - a[i] - 1))