#P18779. [Kaist2021]Three Competitions

[Kaist2021]Three Competitions

Three Competitions

题目描述

编号为 11 到 nn 的人参加了三场比赛。每场比赛的排名都是 11 到 nn 的一个排列,没有并列;排名数字越小,成绩越好。

若 aa 在三场比赛中至少有两场的排名优于 bb,则称 aa 直接战胜 bb。

若存在一个序列 p1,p2,…,pkp_1,p_2,\ldots,p_k,满足 k≥2k\ge2、p1=ap_1=a、pk=bp_k=b,且每个 pip_i 都直接战胜 pi+1p_{i+1},则称 aa 间接战胜 bb。直接战胜也属于间接战胜。两个人可能互相间接战胜对方。

给定所有人的三场排名,回答 qq 次询问:aa 能否间接战胜 bb?

输入格式

第一行一个整数 nn。

接下来 nn 行,第 ii 行三个整数,依次表示第 ii 个人在三场比赛中的排名。每一场的所有排名恰好构成 11 到 nn 的排列。

接下来一行一个整数 qq。

随后 qq 行,每行两个不同的整数 a,ba,b,表示一次询问。

输出格式

对于每次询问输出一行:若 aa 能间接战胜 bb,输出 YES,否则输出 NO。

数据范围

  • 2≤n≤2000002\le n\le200000,1≤q≤2000001\le q\le200000。
  • 1≤a,b≤n1\le a,b\le n,a≠ba\ne b。

样例 1

输入

4
2 4 3
3 1 4
4 3 2
1 2 1
3
1 2
2 1
3 4

输出

YES
YES
NO

样例说明

第 1 人直接战胜第 2 人。第 2 人不能直接战胜第 1 人,但第 2 人战胜第 3 人,第 3 人又战胜第 1 人,因此第 2 人可以间接战胜第 1 人。