루트 노드가 많은 트리일수록 좋은 트리이다

$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$를 잇는 간선이 존재한다.