시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB49323280.000%

문제

$N$ 개의 노드와 $N-1$ 개의 간선으로 이루어진 그래프가 있다. 노드는 $1$번부터 $N$번까지 번호가 매겨져 있으며, 각 간선은 방향성을 가지고 있을 수도 있고, 무방향성일 수도 있다. 모든 간선의 방향성을 제거할 경우 이 그래프는 트리가 된다.

어떤 노드에서 다른 모든 노드로 가는 경로가 존재하는 경우 이 노드를 ‘루트 노드’라고 하자. 이 그래프의 ‘좋음’은 루트 노드의 수로 정의한다. 이 때, 다음 쿼리들을 수행하자.

  1. $u$와 $v$를 잇는 간선을 $u \rightarrow v$의 방향 간선으로 바꾼다.
  2. $u$와 $v$를 잇는 간선을 $u \leftarrow v$의 방향 간선으로 바꾼다.
  3. $u$와 $v$를 잇는 간선을 무방향 간선으로 바꾼다.

쿼리의 실행 결과는 그래프에 누적된다.

입력

첫 번째 줄에는 노드의 수 $N$이 주어진다.

두 번째 줄부터 $N-1$ 개 줄에 걸쳐 간선들에 대한 정보가 주어진다. 간선의 정보는 공백으로 구분된 세 개의 토큰 $U_i$, $D_i$, $V_i$로 주어지며, $U_i$와 $V_i$는 정점 번호를 의미하는 정수이고 $D_i$는 방향을 의미하는 문자열로 -><--- 중 하나이다.

  • $D_i$가 ->라면 $i$번째 간선은 $U_i \rightarrow V_i$인 방향 간선이다.
  • $D_i$가 <-라면 $i$번째 간선은 $U_i \leftarrow V_i$인 방향 간선이다.
  • $D_i$가 --라면 $i$번째 간선은 $U_i \leftrightarrow V_i$인 무방향 간선이다.

다음 줄에는 수행할 쿼리의 수 $Q$가 주어진다.

다음 줄부터 $Q$ 개의 줄의 각 줄마다 쿼리가 순서대로 주어진다. $i$ 번째 줄에는 세 개의 토큰 $u_i$ $d_i$ $v_i$로 주어지며, $u_i$와 $v_i$는 정점 번호를 의미하는 정수이고 $d_i$는 방향을 의미하는 문자열로 -><--- 중 하나이다.

  • $d_i$가 ->라면 $i$번째 간선을 $u_i \rightarrow v_i$인 방향 간선으로 설정한다.
  • $d_i$가 <-라면 $i$번째 간선을 $u_i \leftarrow v_i$인 방향 간선으로 설정한다.
  • $d_i$가 --라면 $i$번째 간선을 $u_i \leftrightarrow v_i$인 무방향 간선으로 설정한다.

출력

쿼리를 수행할 때마다 그래프의 ‘좋음’을 한 줄에 하나씩 출력한다.

제한

  • $2 \le N \le 10^5$
  • $1 \le Q \le 10^5$
  • $1 \le U_i, V_i \le N$ ($1 \le i \le N-1$)
  • $U_i \ne V_i$ ($1 \le i \le N-1$)
  • $U_i$와 $V_i$를 모두 무방향 간선으로 이었을 때 만들어지는 그래프는 트리다.
  • 주어진 그래프에 $u_i$와 $v_i$를 잇는 간선이 존재한다.

예제 입력 1

5
1 -- 2
2 -> 3
2 <- 4
3 -- 5
5
2 -- 4
2 -> 4
5 -> 3
2 -- 3
3 -- 5

예제 출력 1

3
2
0
1
4

출처

Contest > Good Bye, BOJ > Hello, BOJ 2022! E번