コンテスト中に解けなくて、SparseTableを使ってupsolveした！ら、kmjpさんのsubmitをみて確かにそれはそうだ...となった解。 (それまでにあり得るminをとるということで)アプローチは同じなのだけど、データ構造で殴って思考停止になるのはダメ・ゼッタイと思いました。

kmjpさんの回答

題意

問題では写真撮影とされていますが、同じ意味を長方形で示します。

n個 ($1 \leq n \leq 10^5$)の長方形(正方形かもしれない)があります。縦横を$h,w$($1 \leq n \leq 10^9$)とします。それぞれ、$a_1, a_2 ... a_n$として区別します。
各長方形について、それよりも完全に小さい長方形が存在すればそのindexを述べ、存在しなければ-1を出力してください。(つまり、縦か横が"同じではだめ"です。)
各長方形は縦横を入れ替えてもよいです。
複数の候補がある場合、どれを答えてもよいです。

例

「サンプル1」1."3x4", 2"5x4, 3."3x3"があった時、2だけは3よりも大きいです。1はwだけ3よりも大きいですが、hが同じため要件を満たしません。3は1,2を隠すことはできません。[-1, 3, -1]を出力します。
「サンプル」1. 3x6, 2. 4x2があった時、2はひっくり返すと、2x4として扱えます。このため、1にとって2は小さい長方形です。[2, 1]を出力します。
「サンプル」1. 3x3, 2. 3x3があった時、同じ長方形は小さいと呼べないので[-1, -1]です。

問題の言い換え

n個の点があります。それぞれの座標は$x, y$ (ただし、$1 \leq x \le y \leq 10^9$)です。それぞれの点を$a_1, a_2 ... a_n$とします。
各点について、その点よりも左下の座標に点があればそのindexを答えてください。そのような点がない場合は-1を答えてください。

元の題意を考えて、各紙の1点を原点に合わせて$x,y$軸に沿って第一象限に置くとすると、$h,w$を$x,y$として扱ってよいです。それぞれの紙は回転させて良いので、$x \leq y$となるように置いて考えます。(図中青字の「回転」)この時、完全に小さい紙とは、より左下にある点(の紙)であることは明らかです。

考え方1: xを小さい方から見ていく

今、$x$が小さい方からすべての点を見ていくとします。ある程度の点を見た後に、点$a,b$より小さい紙(左下の点)$c,d$を見つけたいとします。

この時、$c$は$a$よりも小さい点であることが必要です。これは、$x$を小さい方から見ているため、すべて走査済みです。ただし、いままで見てきたすべての点には、$x=a$の点も含まれるので、それらを含めてはいけません。(ちょうど$x$の幅は重なってしまうので答えになりません)
$c < a$であるならばその中で高さがbよりも低い点はすべて解になり得ます。つまり、これまでの高さの$min$をとっていればそれが存在するかを確認できます。

上の図で今、紫の点より左下の点を探したいとします。まず、xがより小さい点(頭上はほかのすべての点)が候補になり得ます。このxの点たちを確認するまでのmin(図では赤)が紫の点より低いなら、それは答えです。
もしも、紫の点がこれまでに見てきた点のminと同じか低いなら、答えは存在しません。

    import sys
    input = sys.stdin.readline
    def do():
        import collections
        n = int(input())
        m = collections.defaultdict(list)
        data = []
        datb = []
        for i in range(n):
            a, b = map(int, input().split())
            a, b = min(a,b), max(a,b) #x軸方向を小さい数字にする
            data.append(a)
            datb.append(b)
            m[a].append(i) # 各xの値毎にindex(点)をリストで保存する ための辞書
        mi = 2 ** 60 # 初期値。最初のx in klのループでは答えは存在しない
        ret = -1
        r = [0] * n # 結果
        kl = list(m.keys()) # xを小さい方から見たいので、辞書のキーを小さい方から見ていく
        kl.sort()
        # このループでxが小さい座標から見ていく
        for x in kl:
            # ループ1回目。これは１つ前のxのループまでのminの比較
            for ind in m[x]: # indはそのx座標にいる点のindex
                if mi < datb[ind]: # もし、その点のy座標がこれまでのxのmin(y)より高いなら
                    r[ind] = ret # 答えは存在する
                else:
                    r[ind] = -1 # そうでないなら答えは存在しえない
            # ループ2回目。これは「そのxを含めて」最小のmin(y)を計算する
            for ind in m[x]:
                if datb[ind] < mi:
                    mi = datb[ind]
                    ret = ind + 1 # そのindexを答えように保存
        print(" ".join(list(map(str, r))))
    q = int(input())
    for _ in range(q):
        do()

考え方2: SparseTable

この問題を愚直に考えると
$h$ x $w$の紙があった時、$h-1$までのすべての紙の中で最小の幅が$w-1$ならそれが答えです。つまり、minの値とindexを一緒に返せるRMQ(min)が行えればよいです。(h,wをひっくり返して試行します)。ただし、$1 \leq n \leq 10^9$なので、座標圧縮が必要です。

わざわざ考え方2と書いておいてなんですが、「一辺よりも小さい点の中で、もう一辺がより小さいminと比べる」というアプローチは考え方1と同じです。考え方1では、各エントリ(=xごとの点)を順番に見ていき、1つ小さいxまでのminを保持しながら解を求めており賢いです。

class sparseTable(object):
    func = min

    def __init__(self):
        self.table = []
        self.depthTreeList = 0

    def load(self, l):
        self.n = len(l)
        self.depthTreeList = (self.n - 1).bit_length()  # Level
        self.table.append(l)
        for curLevel in range(1, self.depthTreeList):
            l = []
            for i in range(self.n - (2 ** curLevel - 1)):
                n1 = self.table[curLevel - 1][i]
                n2 = self.table[curLevel - 1][i + (2 ** (curLevel - 1))]
                if n1[0] < n2[0]:
                    l.append(n1)
                else:
                    l.append(n2)
            self.table.append(l)

    def query(self, l, r):  # [l, r)
        diff = r - l
        if diff <= 0:
            raise
        if diff == 1:
            return self.table[0][l]
        level = (diff - 1).bit_length() - 1
        n1 = self.table[level][l]
        n2 = self.table[level][r - (2 ** level)]
        if n1[0] < n2[0]:
            return n1
        else:
            return n2

def do():
    import sys
    input = sys.stdin.readline

    from bisect import bisect_left, bisect_right
    n = int(input())
    dat = []
    INF = 2**60
    zatsu = set()
    for i in range(n):
        num = i + 1
        a, b = map(int, input().split())
        a,b = min(a,b), max(a,b)
        zatsu.add(a)
        zatsu.add(b)
        dat.append([a, b, num])
    if n == 1:
        print("-1")
        return

    # 座標圧縮
    zatsu = list(zatsu)
    zatsu.sort()
    zatsu = list(enumerate(zatsu))
    zTable = dict()
    for i in range(len(zatsu)):
        zTable[zatsu[i][1]] = zatsu[i][0]
    sList = [[INF, -1] for i in range( len(zatsu))]
    # 座標圧縮に点を対応させるとともに、Sparse Tableに乗せるテーブルを作る
    for i in range(n):
        a,b,num = dat[i]
        a,b = zTable[a], zTable[b]
        dat[i][0] = a
        dat[i][1] = b
        if sList[a][0] > b:
            sList[a] = [b, num]
        if sList[b][0] > a:
            sList[b] = [a, num]

    st = sparseTable()
    st.load(sList)
    res = []

    # w, hを総当たりで、-1までの区間にもう一方より小さい点があるかを確認
    # あるなら、そのindexを答えとする
    for i in range(n):
        a,b,num = dat[i]
        xres = -1
        if a > 0:
            x = st.query(0, a)
            if x[0] != INF and x[0] < b:
                xres = x[1]
        if b > 0:
            x = st.query(0, b)
            if x[0] != INF and x[0] < a:
                xres = x[1]
        res.append(xres)
    print(" ".join(list(map(str, res))))

q = int(input())
for _ in range(q):
    do()