City X consists of n vertical and n horizontal infinite roads, forming n × n intersections. Roads (both vertical and horizontal) are numbered from 1 to n, and the intersections are indicated by the numbers of the roads that form them.

Sand roads have long been recognized out of date, so the decision was made to asphalt them. To do this, a team of workers was hired and a schedule of work was made, according to which the intersections should be asphalted.

Road repairs are planned for n^2 days. On the i-th day of the team arrives at the i-th intersection in the list and if none of the two roads that form the intersection were already asphalted they asphalt both roads. Otherwise, the team leaves the intersection, without doing anything with the roads.

According to the schedule of road works tell in which days at least one road will be asphalted.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 50) — the number of vertical and horizontal roads in the city. 

Next n^2 lines contain the order of intersections in the schedule. The i-th of them contains two numbers h_{i}, v_{i} (1 ≤ h_{i}, v_{i} ≤ n), separated by a space, and meaning that the intersection that goes i-th in the timetable is at the intersection of the h_{i}-th horizontal and v_{i}-th vertical roads. It is guaranteed that all the intersections in the timetable are distinct.


-----Output-----

In the single line print the numbers of the days when road works will be in progress in ascending order. The days are numbered starting from 1.


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

Output
1 4 

Input
1
1 1

Output
1 



-----Note-----

In the sample the brigade acts like that:  On the first day the brigade comes to the intersection of the 1-st horizontal and the 1-st vertical road. As none of them has been asphalted, the workers asphalt the 1-st vertical and the 1-st horizontal road;  On the second day the brigade of the workers comes to the intersection of the 1-st horizontal and the 2-nd vertical road. The 2-nd vertical road hasn't been asphalted, but as the 1-st horizontal road has been asphalted on the first day, the workers leave and do not asphalt anything;  On the third day the brigade of the workers come to the intersection of the 2-nd horizontal and the 1-st vertical road. The 2-nd horizontal road hasn't been asphalted but as the 1-st vertical road has been asphalted on the first day, the workers leave and do not asphalt anything;  On the fourth day the brigade come to the intersection formed by the intersection of the 2-nd horizontal and 2-nd vertical road. As none of them has been asphalted, the workers asphalt the 2-nd vertical and the 2-nd horizontal road.

Difficulty: interview

Starter code:

Solutions:
n = int(input())
h = [False] * n
v = [False] * n
result = [ ]
for i in range(n * n):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    if not h[a] and not v[b]:
        h[a] = v[b] = True
        result.append(i + 1)
print(' '.join(map(str, result)))


n = int(input())

hl = []
vl = []
z = []

for i in range(n**2):
    a,b = list(map(int, input().split()))
    if a in hl or b in vl:
        pass
    else:
        z.append(str(i+1))
        hl.append(a)
        vl.append(b)
print(' '.join(z))


n  = int(input())
ans = []
vert = set()
hor = set()
for i in range(n*n):
    a,b = map(int,input().split())
    if a not in vert and b not in hor:
        ans.append(i+1)
        vert.add(a)
        hor.add(b)
print(*ans)

n = int(input())
a, b = [0] * n, [0] * n
for x in range(n ** 2):
    i, j = map(int, input().split())
    if (not a[i - 1]) and (not b[j - 1]):
        print(x + 1, end = ' ')
        a[i - 1] = b[j - 1] = 1
print()


n = int(input())
li = [[0] * n for i in range(n)]
for i in range(n * n):
    a, b = [int(i) for i in input().split()]
    if (li[a - 1][b - 1] == 0):
        for j in range(n):
            li[j][b - 1] = 1
            li[a - 1][j] = 1
        print(i + 1, end = ' ')

n = int(input())
rs = [0 for i in range(n+1)]
cs = [0 for i in range(n+1)]
s = ""
for i in range(n**2):
    r, c = list(map(int, input().split()))
    if rs[r] == 0 and cs[c] == 0:
        rs[r] = 1
        cs[c] = 1
        s += str(i+1)+" "
print(s)
    


n = int(input())
res = []
used = [False] * n
used1 = [False] * n
for i in range(n * n):
    x, y =[int(x) for x in input().split()]
    if used[x - 1] == False and used1[y - 1] == False:
        res.append(i + 1)
        used[x - 1] = True
        used1[y - 1] = True
print(*res)

n = int(input())
h = [False for i in range(n)]
v = [False for i in range(n)]
z = []
for i in range(n*n):
    a,b = list(map(int, input().split()))
    a -= 1
    b -= 1
    if (not h[a]) and (not v[b]):
        z.append(i+1)
        h[a] = True
        v[b] = True
print(*z)


n=int(input())
sa=set()
sb=set()
l=[]
for i in range(n*n):
  a,b=list(map(int,input().split()))
  if not(a in sa) and not(b in sb):
    l+=[str(i+1)]
    sa.add(a)
    sb.add(b)
print(' '.join(l))


n = int(input())
ys = [False for i in range(n)]
xs = [False for i in range(n)]
res = []

for i in range(1, n*n+1):
    x, y = list(map(int, input().split(' ')[:2]))
    x -= 1
    y -= 1
    if not ys[y] and not xs[x]:
        res.append(i)
        ys[y] = True
        xs[x] = True

print(*res)


import sys


#sys.stdin = open("input.txt")
#sys.stdout = open("output.txt", "w")

n = int(input())

vert = [False for i in range(n)]
gor = [False for i in range(n)]

for i in range(n ** 2):
	x, y = [int(i) - 1 for i in input().split()]
	if not vert[x] and not gor[y]:
		vert[x] = True
		gor[y] = True
		print(i + 1, end = ' ')

print()

n = int(input())

tmp_h = [False]*(n+1)
tmp_v = [False]*(n+1)

answer = []
for i in range(1, n**2+1):
	h, v = map(lambda x: int(x)-1, input().split())
	if not tmp_h[h] and not tmp_v[v]:
		tmp_h[h] = True
		tmp_v[v] = True
		answer.append(i)

print(' '.join(map(str, answer)))

import sys
lines = iter(sys.stdin.read().split("\n"))
n = int(next(lines))
rows = [0] * (n + 1)
cols = [0] * (n + 1)
res = []
for i in range(n ** 2):
    r, c = list(map(int, next(lines).strip(" ").split(" ")))
    if rows[r] == 0 and cols[c] == 0:
        rows[r] = 1
        cols[c] = 1
        res.append(str(i + 1))
print(" ".join(res))


#! /usr/bin/python

n = int(input())
v = [0 for i in range(n)]
h = [0 for i in range(n)]

ans = []

for i in range(n ** 2):
    ch, cv = list(map(int, input().split()))
    if v[cv - 1] == 0 and h[ch - 1] == 0:
        v[cv - 1] = 1
        h[ch - 1] = 1
        ans.append(i + 1)

print(' '.join(list(map(str, ans))))


n=int(input())
m1=[0 for i in range(n)]
m2=[0 for i in range(n)]
for i in range(n*n):
	a,b=list(map(int,input().split()))
	if m1[a-1]==m2[b-1]==0:
		m1[a-1]=m2[b-1]=1
		print(i+1,end=' ')

n = int(input())
a = []
b = []
for i in range(1, n*n+1):
    x, y = map(int, input().split())
    if x not in a and y not in b:
        print(i, end=' ')
        a.append(x)
        b.append(y)


n = int(input())
res = []
x = set()
y = set()
for i in range(n*n):
    a,b = map(int,input().split())
    if not (a in x or b in y):
        x.add(a)
        y.add(b)
        res.append(i+1)
print(*res)

3

import itertools as ittls
from collections import Counter

from pprint import pprint as pprint

import re
import math


def sqr(x):
    return x*x

def inputarray(func=int):
    return list(map(func, input().split()))

# --------------------------------------
# --------------------------------------

N = int(input())

maskrow = [0]*N
maskcol = [0]*N
res = []

for i in range(N*N):
    x, y = inputarray(lambda x: int(x) - 1)

    if maskrow[x] == 0 and maskcol[y] == 0:
        res.append(i)

        maskrow[x] = 1
        maskcol[y] = 1

print( ' '.join([str(x + 1) for x in res]) )


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

n = int(input())
H = [False for i in range(n+1)]
V = [False for i in range(n+1)]
ans = []

for i in range(n**2):
    h,v = list(map(int,input().split()))
    if not H[h] and not V[v]:
        H[h] = True
        V[v] = True
        ans.append(i+1)
print(' '.join(map(str,ans)))


N = int(input())
paintH = set()
paintV = set()
d = 0
res = []
for i in range(N):
    for j in range(N):
        d += 1
        h, v = list(map(int, input().split()))
        if h not in paintH and v not in paintV:
            paintH.add(h)
            paintV.add(v)
            res.append(str(d))

print(" ".join(res))


n = int(input())
m = n**2
L = [list(map(int, input().split())) for _ in range(m)]
H = [ 0 for _ in range(n)]
V = [ 0 for _ in range(n)]
R = ""
for k in range(m):
    i = L[k][0]-1
    j = L[k][1]-1
    if H[i] == 0 and V[j] == 0:
        H[i] = 1
        V[j] = 1
        R = R + str(k+1) + ' '
print(R)

n=int(input())
hor=set()
ver=set()
res=[]
for i in range(n*n):
	h,v=map(int, input().split())
	if (h not in hor) and (v not in ver):
		res.append(str(i+1))
		hor.add(h)
		ver.add(v)
print(" ".join(res))