시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB134261818.947%

문제

A젖소와 D젖소가 평면그래프 게임을 한다. 이 게임은 처음에 N개의 정점과 M개의 간선으로 이루어진 평면그래프에서 진행된다. 

이 때 게임은 주어진 수에 따라 두 가지 행동을 Q번 진행한다. 

  • 1 u v : 정점 u와 정점 v를 잇고 있던 간선이 있다면 그 간선을 삭제한다. 

  • 2 u v : 정점 u와 정점 v가 같은 컴포넌트에 속해 있는지 확인한다. 두 정점이 같은 컴포넌트에 속해 있으면 A젖소, 그렇지 않으면 D젖소의 승리이다.

원래는 2번 행동마다 어떤 젖소가 이길지 알아내면 되는 거였으나... 자신이 많이 이기지 못할걸 알아버린 험악한 D젖소는 화가 났다.

그래서 주어지는 모든 행동에서 주어지는 수를 다음과 같은 규칙으로 (u, v)에서 (u', v')으로 바꿔버리려고 한다.

어떤 행동이 있기 전까지의 모든 2번 행동 중 A젖소가 이긴 횟수를 a라고 했을 때 u' = (- 1 + X × a) mod N + 1이고, v' = (- 1 + Y × a) mod N + 1이다. (단, x mod yxy로 나눈 나머지를 의미한다.)

이제 D젖소는 만족했다. 2번 행동을 할 때마다 어떤 젖소가 이기게 될지 알아보자!

입력

첫째 줄에는 다섯 개의 양의 정수 N, M, Q, X, Y가 주어진다.

1+i번째 줄에는 i번 정점의 좌표 xi와 yi가 주어진다.

N+1+j번째 줄에는 각 간선의 양 끝점 aj, bj 가 주어진다. 이는 j번째 간선이 aj번 정점과 bj번 정점을 양 끝점으로 갖는 선분 모양의 간선임을 의미한다.

N+M+2번째 줄부터 Q개의 줄에는 각 줄마다 하게 될 행동을 의미하는 세 정수가 주어진다. 실제로는 u', v'을 이용하여 행동을 처리해야 함에 유의하라.

출력

2번 행동을 할 때마다 A젖소가 이기게 된다면 A를, D젖소가 이기게 된다면 D를 한 줄에 출력한다.

제한

  • 1 ≤ N, M, Q, X, Y ≤ 100000
  • -109​ ≤ xi, yi ≤ 109
  • 1 ≤ aj, bjN
  • 모든 행동에 대해서 1 ≤ u, vN
  • 2번 행동이 한 번 이상 주어짐이 보장된다.
  • 주어진 그래프는 평면 그래프임이 보장된다. 즉, 서로 다른 두 간선은 끝점을 제외한 다른 점에서 만나지 않는다.

예제 입력 1

6 5 6 1 2
0 0
0 2
-3 0
-2 -2
1 -1
4 0
1 4
1 6
3 4
4 5
5 6
1 5 6
2 2 4
1 5 6
2 1 3
1 6 4
2 6 4

예제 출력 1

D
A
D

출처

Contest > BOJ User Contest > Semi-Game Cup > Semi-Game Cup E번

  • 데이터를 추가한 사람: jhnah917
  • 문제를 만든 사람: maruii