나무늘보

나무늘보는 나쁘지, 알겠어? 그래서 우리는 게으른 녀석들을 벌주기 위한 문제를 준비하기로 했다.

트리가 주어진다. 트리에서 간선 하나를 제거한 다음 간선 하나를 추가하여, 최종 그래프가 트리이면서 완전 매칭을 갖도록 하는 방법의 수를 세어야 한다. 제거한 간선이나 추가한 간선이 같지 않으면 두 연산 방법은 서로 다른 것으로 간주한다. 제거한 간선과 추가한 간선은 같을 수 있다.

완전 매칭은 각 정점이 이 간선들 가운데 정확히 하나의 끝점이 되도록 하는 간선의 부분집합이다.

첫째 줄에 정점의 수 n (2 ≤ n ≤ 5·105)이 주어진다.

다음 n - 1개의 각 줄에는 하나의 간선의 양 끝점인 두 정수 a와 b (1 ≤ a, b ≤ n)이 주어진다. 그래프가 트리임이 보장된다.

문제의 답을 나타내는 정수 하나를 출력한다.

첫 번째 예제에는 8가지 방법이 있다:

• 2와 3 사이의 간선을 1과 3 사이의 간선으로 바꾼다,
• 2와 3 사이의 간선을 1과 4 사이의 간선으로 바꾼다,
• 2와 3 사이의 간선을 2와 3 사이의 간선으로 바꾼다,
• 2와 3 사이의 간선을 2와 4 사이의 간선으로 바꾼다,
• 1과 2 사이의 간선을 1과 2 사이의 간선으로 바꾼다,
• 1과 2 사이의 간선을 1과 4 사이의 간선으로 바꾼다,
• 3과 4 사이의 간선을 1과 4 사이의 간선으로 바꾼다,
• 3과 4 사이의 간선을 3과 4 사이의 간선으로 바꾼다.