루트가 많은 트리?

우리가 보통 알고 있는 트리는 간선에 방향이 없지만, 다음과 같이 방향이 있는 간선들로 이루어진 트리를 정의할 수 있다.

• 트리의 루트는 진입 차수 (indegree)가 $0$인 정점이다.
• 루트를 제외한 모든 정점은 간선의 방향을 따라서 루트로부터 이 정점까지 경로가 존재한다.
• 루트를 제외한 정점은 정확히 하나의 부모 정점을 가진다.

$1$부터 $N$까지 번호가 매겨져 있는 $N$ 개의 정점이 있는 방향이 없는 간선들로 이루어진 트리가 주어진다. 이 트리의 모든 간선에 대해서, 방향을 지정해 주려고 한다. 어떤 간선은 방향이 지정되어 있고, 어떤 간선은 아직 방향이 지정되지 않은 상태이다.

방향이 지정되지 않은 간선에 어떤 방향을 주는가에 따라, 이 그래프는 트리가 될 수도 있고 아닐 수도 있다. 만약 트리가 된다면, 이 트리에는 위에서 정의한 루트 정점이 하나 존재한다.

입력으로 주어진 트리에 대해서 간선들에 방향을 정했을 때, 트리의 루트가 될 수 있는 정점의 개수를 구하라.

입력 형식

첫 줄에 트리의 정점 개수를 나타내는 정수 $N$이 주어진다. ($1 \le N \le 300\,000$)

그 다음 줄부터 $N-1$ 개의 줄에 걸쳐, 각 줄마다 간선 하나의 정보를 나타내는 세 정수가 공백으로 구분되어 주어진다. 만약, 정점 $a$와 정점 $b$를 잇는 간선에 방향이 정해지지 않았다면, 이는 a b 0으로 표현된다. 만약 정점 $a$에서 시작해서 정점 $b$로 가는 방향이 정해진 간선이라면, 이는 a b 1로 표현된다.

방향 정보를 무시한다면, 주어진 그래프는 트리임에 유의하라.

출력 형식

첫 줄에 방향이 정해지지 않은 간선의 방향을 정했을 때 그 결과가 루트가 있는 트리가 되고, 이때 루트가 될 수 있는 정점들의 개수를 출력한다.

예제

8
5 2 0
8 1 0
5 7 0
4 1 0
5 1 0
3 1 1
5 6 1

1

예제 설명

이 그림을 보면, 정점 $3$은 정점 $1$을 향해 나가는 간선밖에 없기 때문에 다른 정점에서 이 정점으로 들어올 수 없다. 따라서 다른 정점은 루트가 될 수 없으며, 정점 $3$이 루트가 될 수 있는지만 확인해보자. 오른쪽 그림과 같이 다른 간선들에 방향을 정하면 정점 $3$이 루트가 될 수 있음을 알 수 있다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

해설