대피

끔찍한 일이 일어났다. 닥터 옥타비우스가 산업 연구소를 점거했다. 연구소는 $n$개의 방으로 이루어져 있고, 일부 방은 복도로 연결되어 있다. 복도는 총 $n-1$개이며, 어느 방에서든 다른 모든 방으로 갈 수 있다. 즉, 연구소는 $n$개의 정점을 가진 트리이다. 각 복도마다 한쪽 끝에서 다른 쪽 끝까지 이동하는 데 걸리는 시간 $l_i$가 주어진다. 복도는 양방향으로 통행할 수 있다.

각 방에는 사람이 한 명씩 있다. 닥터 옥타비우스는 이 사람들을 모두 죽이려 하지만, 살아날 기회를 주었다. 출구는 트리의 잎에 있다. 잎은 차수가 $0$ 또는 $1$인 정점이다. 출구에 도착한 사람은 옥타비우스의 촉수에서 벗어난다. 각 복도에는 악당이 설치한 기폭 장치가 있고, 장치마다 폭발 시각 $t_i$가 정해져 있다. 장치가 폭발하면 그 복도는 더 이상 지날 수 없고, 폭발 순간 복도 안에 있던 사람은 죽는다. 폭발 순간에 복도의 끝까지 도착한 사람은 살아남는다.

스파이더맨은 제때 도울 수 없으므로 사람들은 스스로 살아남아야 한다. 살아남을 수 있는 최대 인원을 구하라.

첫 줄에 방의 개수 $n$ ($1 \le n \le 100000$)이 주어진다. 다음 $n-1$개의 줄에는 네 개의 정수 $a_i$, $b_i$, $l_i$, $t_i$ ($1 \le a_i, b_i \le n$; $1 \le l_i \le 10000$; $1 \le t_i \le 10^9$)가 주어진다. 각각 복도가 잇는 두 방의 번호, 복도를 통과하는 데 걸리는 시간, 그 복도의 기폭 장치가 폭발하는 시각이다.

주어지는 연구소는 트리임이 보장된다.

살아남을 수 있는 최대 인원을 한 줄에 출력한다.

첫 번째 예시에서 5번 방의 사람은 4번 방으로 달린다. 3번 방의 사람도 같은 방으로 향한다. 이 사람은 폭발 시각에 도착하지만 그래도 살아남는다.

두 번째 예시에서 4번 방의 사람은 2번 방으로, 1번 방의 사람은 5번 방으로 향한다. 3번 방의 사람은 살아남지 못한다.