음양의 조화

청년농부인 윤호는 아침 산책을 계획하고 있습니다. 농장은 트리구조로 이루어져 있으며, N개의 헛간(1<= N <= 100,000)들이 N-1개의 경로를 통해 연결되어 있어, 어떤 헛간에서도 다른 헛간으로 갈 수 있습니다. 윤호는 다시 지나가지 않을 두 개의 다른 헛간을 출발점과 도착점으로 선택하여 경로를 설정하려고 한다. 그리고 그의 산책 경로가 장기간 시간이 소요되는 것을 고려하여, 이 경로에 위치하고 있는 또 다른 '휴식처' 헛간도 선택하려고 한다(출발점과 도착점을 제외하고).

각 경로에는 찰코나 (Charcolais; 흰색 털) 또는 앵거스 (Angus; 검은색 털) 품종의 소 무리가 있다. 윤호는 그의 산책 중에 음과 양의 힘이 균형을 이루기를 원합니다. 즉, 찰코나 무리와 앵거스 무리의 수가 같아지도록 경로를 설정하려고 한다-- 출발점에서 휴식처까지, 그리고 휴식처에서 도착점까지.

윤호는 위와 같이 "균형잡힌" 경로를 얼마나 다르게 선택할 수 있는지 궁금해합니다. 두 경로가 다르다는 것은 그들이 다른 세트의 경로로 구성되어 있다는 것이다; 경로는 그것이 균형잡혀 있다면 경로를 통해 다수의 유효한 '휴식처' 위치가 있더라도 한 번만 계수된다.

윤호가 선택할 수 있는 경로의 수를 결정하는 데 도움을 주세요!

• 첫 번째 줄 : 정수 N.
• 두 번째 줄..N 번째 줄 : 세 개의 정수 a_i, b_i 그리고 t_i는 경로 i가 연결하는 두 개의 헛간을 나타낸다. t_i는 그 경로를 따라서 있는 소 무리가 찰코나이면 0, 앵거스라면 1이다.

• 첫 번째 줄 : 한 정수, 윤호가 선택할 수 있는 가능한 경로의 수를 나타낸다.