페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8515
서브태스크

구조조정 1s 1024MB

문제

정올 주식회사는 N명의 직원으로 이루어져 있다.

정확히 1명의 회장을 제외한 나머지 모든 직원은, 본인의 직속 상사를 정확히 한 명 가지고 있으며,
모든 직원은 자신의 상사를 따라서 계속 올라간다면 결국 회장을 만나게 될 때, 이 구조를 '안정적인 회사' 라 부른다.

어느 날 구조조정의 시간이 다가왔다. 이 구조조정은 다음과 같이 이루어진다.

  • 서로 다른 두 직원 a와 b를 뽑는다. 이때 둘은 직원 - 직속 상사 관계임이 보장된다.
    (누가 상사인지는 모른다, 또한 회장도 여기에 뽑힐 수 있다.)

  • 두 직원의 관계를 역전한다. 즉, a와 b의 직원 - 직속 상사 관계를 뒤바꾼다.

물론, 마구잡이식의 구조조정은 '안정적인 회사'를 유지할 수 없게 한다.

구조조정안 Q개에 대해, 각 조정안의 결과가 '안정적인 회사'인지 판별해보자.

각 조정안은 순서대로 제공되며, 이 조정안은 누적된다.

즉, i번째 조정안은 i-1번째 조정안을 적용한 상태에서 직원 쌍 하나를 추가로 역전시키는 안이다.

초기 상태가 안정적인 회사가 아닐수도 있음에 유의하라.

그러나, 모든 테스트 케이스에 대해, 적절한 구조조정안을 통해 안정적인 회사를 만들 수 있다는 보장을 할 수 있다.


입력

첫 줄에 직원의 수 N이 주어진다. (1\leq N\leq 3*10^5)

그 다음 N-1개 줄에 걸쳐, 현재 회사의 직원 관계가 u_i\ \ v_i의 형태로 주어진다. (1\leq u_i, v_i\leq N)

이때 u_i가 직속 상사의 번호고, v_i가 직원의 번호이다.

그 다음 구조조정안의 수 Q가 주어진다. (0\leq Q\leq 10^6)

그 다음 Q개의 줄에 걸쳐 각 구조조정안의 정보가 a_i \ \ b_i의 형태로 주어진다. (1\leq a_i, b_i\leq N)


출력

Q+1개의 줄에 걸쳐, i번째 줄에는 i-1번 구조조정안까지 적용된 후 회사가 안정적인지를 출력하여라.

즉, 첫 줄에는 처음 상태가 안정적인지를 출력하면 된다.

안정적인 회사라면 DA, 그렇지 않다면 NE를 출력하여라.


부분문제

번호 점수 조건
#17점

N\leq 300, Q=0

#212점

N\leq 300, Q\leq 300

#316점

N\leq 1000, Q\leq 1000

#415점

Q=0

#523점

모든 u_i와 v_i에 대해, u_i=v_i+1이거나 u_i=v_i-1이다.

#627점

추가 제한 없음


예제 #1

3
1 2
1 3
3
1 2
1 2
1 3
DA
DA
DA
DA

예제 #2

4
2 1
2 3
1 4
4
4 1
4 1
3 2
1 4
DA
NE
DA
DA
NE


출처

COCI 2024/2025 Contest #1
로그인해야 코드를 작성할 수 있어요.