output_description: Print N lines. In i-th line print the answer to the question when k = i.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      x_1 y_1
      x_2 y_2
      :
      x_N y_N
attempt: class UnionFind():
    def __init__(self,n):
      self.n=n
      self.root=[-1]*(n+1)
      self.rank=[0]*(n+1)
    def FindRoot(self,x):
      if self.root[x]<0:
        return x
      else:
        self.root[x]=self.FindRoot(self.root[x])
        return self.root[x]
    def Unite(self,x,y):
      x=self.FindRoot(x)
      y=self.FindRoot(y)
      if x==y:
        return
      else:
        if self.rank[x]>self.rank[y]:
          self.root[x]+=self.root[y]
          self.root[y]=x
        elif self.rank[x]<=self.rank[y]:
          self.root[y]+=self.root[x]
          self.root[x]=y
          if self.rank[x]==self.rank[y]:
            self.rank[y]+=1
    def isSameGroup(self,x,y):
      return self.FindRoot(x)==self.FindRoot(y)
    def Count(self,x):
      return -self.root[self.FindRoot(x)]
    
  n=int(input())
  uf=UnionFind(n)
  arr=[list(map(int,input().split()))+[i+1] for i in range(n)]
  arr=sorted(arr,key=lambda x:x[0])
  x,y,i=arr[0]
  tmp=[]
  for tx,ty,j in arr:
    if y<=ty:
      uf.Unite(i,j)
      for tx2,ty2,j2 in tmp:
        if ty2<=ty:
          uf.Unite(j,j2)
      tmp=[]
    else:
      tmp.append([x,y,i])
      x=tx
      y=ty
      i=j
  arr=sorted(arr,reverse=True,key=lambda x:x[1])
  x,y,i=arr[0]
  tmp=[]
  for tx,ty,j in arr:
    if x>=tx:
      uf.Unite(i,j)
      for tx2,ty2,j2 in tmp:
        if tx2>=tx:
          uf.Unite(j,j2)
      tmp=[]
    else:
      tmp.append([x,y,i])
      x=tx
      y=ty
      i=j
  for i in range(1,n+1):
    print(uf.Count(i))
problem_description: Statement
  
  There are N cities on a 2D plane. The coordinate of the i-th city is (x_i,
  y_i). Here (x_1, x_2, \dots, x_N) and (y_1, y_2, \dots, y_N) are both
  permuations of (1, 2, \dots, N).
  
  For each k = 1,2,\dots,N, find the answer to the following question:
  
  Rng is in City k. Rng can perform the following move arbitrarily many times:
  
    * move to another city that has a smaller x-coordinate and a smaller y-coordinate, or a larger x-coordinate and a larger y-coordinate, than the city he is currently in.
  
  How many cities (including City k) are reachable from City k?
samples: [{"input": "4\n    1 4\n    2 3\n    3 1\n    4 2", "output": "1\n    1\n    2\n    2\n    \n\nRng can reach City 4 from City 3, or conversely City 3 from City 4.\n\n* * *"}, {"input": "7\n    6 4\n    4 3\n    3 5\n    7 1\n    2 7\n    5 2\n    1 6", "output": "3\n    3\n    1\n    1\n    2\n    3\n    2"}]