순열 그래프의 전갈성 판별

컴퓨터 과학에서 다루는 그래프 가운데, 간선에 방향이 없는 무향 그래프를 생각해 보자. 무향 그래프 중 일부는 특별한 성질을 가진다.

• 임의의 두 정점 사이에 항상 경로가 존재하는 그래프가 있다. 이런 그래프를 연결 그래프라고 부른다.
• 사이클이 하나도 없는 그래프가 있다. 이런 그래프를 포레스트라고 부른다.
• 사이클이 하나도 없으면서 임의의 두 정점 사이에 경로가 존재하는 그래프가 있다. 이런 그래프를 트리라고 부른다.
• 전갈스러운 성질을 가지는 그래프도 있다. 이런 그래프를 전갈 그래프라고 부른다.

연결 그래프	포레스트	트리	전갈 그래프

이 문제에서 다루는 것은 전갈 그래프다. 전갈스러운 성질은 다음과 같이 정의한다.

• 그래프는 연결 그래프다.
• 모든 정점은 아래 네 종류 중 하나에 속한다.
  • 가시 가시 정점은 정확히 하나이며, 꼬리 정점하고만 연결되어 있다.
  • 꼬리 꼬리 정점은 정확히 하나이며, 가시 정점과 몸통 정점하고만 연결되어 있다.
  • 몸통 몸통 정점은 정확히 하나이며, 꼬리 정점과 모든 발 정점하고만 연결되어 있다.
  • 발 가시, 꼬리, 몸통이 아닌 정점은 모두 발 정점이다. 각 발 정점은 반드시 몸통 정점과 연결되어 있고, 꼬리 정점이나 가시 정점과는 연결되어 있지 않다. 발 정점끼리는 연결되어 있어도 되고, 연결되어 있지 않아도 된다.

위 그림은 전갈 그래프의 예다.

컴퓨터 과학자들이 전갈스러움이라는 성질을 찾아내고 이름까지 붙인 까닭은 판별 비용이 독특하기 때문이다. $N \times N$ 크기의 인접 행렬이 주어졌을 때, 자명하지 않은 그래프 성질(연결 그래프, 포레스트, 트리 등)은 대개 입력을 읽는 시간을 빼고도 $O(N^2)$ 시간이 있어야 판별할 수 있다. 그런데 전갈성은 간선의 개수와 상관없이, 입력을 읽는 시간을 빼면 언제나 $O(N)$ 시간에 판별하는 알고리즘이 있다.

재현이는 이 성질에 감탄해서, 순열 그래프라는 또 하나의 독특한 그래프를 주고 그 그래프가 전갈스러운지 판별하는 문제를 냈다. 길이가 $N$인 순열 $A_1, A_2, \dots, A_N$이 나타내는 순열 그래프는 다음과 같이 정의한다.

• 그래프는 $1$번부터 $N$번까지 번호가 붙은 정점 $N$개로 이루어진다.
• 간선은 다음 과정으로 잇는다.
  1. 평행한 두 직선을 긋고, 한 직선 위에는 $1, 2, \dots, N$을, 다른 직선 위에는 $A_1, A_2, \dots, A_N$을 차례로 적는다.
  2. 같은 수끼리 선분으로 잇는다.
  3. $i$끼리 이은 선분과 $j$끼리 이은 선분이 교차하는 모든 쌍 $(i, j)$에 대해, $i$번 정점과 $j$번 정점을 무향 간선으로 잇는다.

위 그림은 $A = [2, 5, 4, 1, 3]$이 나타내는 순열 그래프다.

문제를 조금 더 어렵게 만들고 싶었던 재현이는 순열의 두 원소를 교환하는 연산을 $Q$개 덧붙였다. 각 교환 연산을 수행한 뒤의 순열 그래프가 전갈 그래프인지 판별하라. 교환은 일시적이지 않고, 이후의 연산에 그대로 남는다.

첫째 줄에 순열의 길이 $N$ ($4 \le N \le 100000$)이 주어진다.

둘째 줄에 순열 $A$를 이루는 서로 다른 자연수 $A_1, A_2, \dots, A_N$ ($1 \le A_i \le N$)이 주어진다.

셋째 줄에 교환 연산의 개수 $Q$ ($1 \le Q \le 100000$)가 주어진다.

이어지는 $Q$개의 줄에 교환 연산이 한 줄에 하나씩 주어진다. 각 줄에는 두 자연수 $x$와 $y$ ($1 \le x, y \le N$, $x \ne y$)가 공백을 사이에 두고 주어진다. 순열 $A$의 $x$번째 원소 $A_x$와 $y$번째 원소 $A_y$를 먼저 교환한 뒤, 그 순열 $A$가 나타내는 순열 그래프가 전갈 그래프인지 판별해서 출력하라는 뜻이다.

각 교환 연산마다, 교환한 뒤의 순열 $A$가 나타내는 순열 그래프가 전갈 그래프면 YES를, 그렇지 않으면 NO를 한 줄에 하나씩 출력한다.