// Author: Luka Kalinovcic #include #include #include using namespace std; #define MAX 300000 #define MOD 1000000007 int n; int parent[MAX + 1]; int n_adj[MAX + 2]; int adj[MAX + 1][3]; int next_node[MAX + 1]; int next_fork[MAX + 1]; int next_fork_dist[MAX + 1]; vector traversal; void AddArc(int u, int v) { if (n_adj[u] == 3 || n_adj[v] == 3) { printf("0\n"); exit(0); } adj[u][n_adj[u]++] = v; adj[v][n_adj[v]++] = u; } void ComputeTraversal() { parent[0] = -1; traversal.reserve(n + 1); traversal.push_back(0); for (int i = 0; i < traversal.size(); ++i) { int u = traversal[i]; for (int j = 0; j < n_adj[u]; ++j) { int v = adj[u][j]; if (v == parent[u]) continue; parent[v] = u; traversal.push_back(v); } } } bool GetNeighbour(int u, int a, int b, int *c) { bool first = true; *c = -1; for (int i = 0; i < n_adj[u]; ++i) { if (adj[u][i] != a && adj[u][i] != b) { if (!first) return false; first = false; *c = adj[u][i]; } } return true; } void ComputeNextFork() { for (int i = n; i >= 1; --i) { int u = traversal[i]; if (n_adj[u] == 2) { int v; GetNeighbour(u, parent[u], -1, &v); next_fork[u] = next_fork[v]; next_fork_dist[u] = next_fork_dist[v] + 1; } else { next_fork[u] = u; next_fork_dist[u] = 0; } } } bool IsTerminal(int x) { return n_adj[next_fork[x]] == 1; } int dp[MAX + 1][4][4]; void Transition(int x, int* y) { *y += x; if (*y >= MOD) *y -= MOD; } int Solve() { dp[0][1][0] = 1; int result = 0; for (int u : traversal) { for (int i = 0; i <= n_adj[u]; ++i) { int v = (i == n_adj[u]) ? n + 1 : adj[u][i]; for (int j = 0; j <= n_adj[v]; ++j) { int w = (j == n_adj[v]) ? n + 1 : adj[v][j]; if (dp[u][i][j] == 0) continue; int x, y; if (!GetNeighbour(u, parent[u], v, &x) || !GetNeighbour(v, u, w, &y)) { continue; } if (x != -1 && y != -1) { while (n_adj[x] == 2 && n_adj[y] == 2) { GetNeighbour(x, parent[x], -1, &x); GetNeighbour(y, parent[y], -1, &y); } if (!GetNeighbour(x, parent[x], -1, &x) || !GetNeighbour(y, parent[y], -1, &y)) { continue; } } if (x == -1) swap(x, y); if (x == -1) { Transition(dp[u][i][j], &result); continue; } Transition(dp[u][i][j], &dp[x][n_adj[x]][0]); for (int ii = 0; ii < n_adj[x]; ++ii) { y = adj[x][ii]; if (y == parent[x]) continue; Transition(dp[u][i][j], &dp[x][ii][n_adj[y]]); } if (IsTerminal(x)) { if (next_fork_dist[x] >= 3 && next_fork_dist[x] % 2 == 1) { Transition(dp[u][i][j], &result); } } else { for (int iter = 0, a = next_fork[x]; iter < 2 && a != x; ++iter, a = parent[a]) { for (int ii = 0; ii < n_adj[a]; ++ii) { int b = adj[a][ii]; if (b == parent[a]) continue; for (int jj = 0; jj < n_adj[b]; ++jj) { int c = adj[b][jj]; if (c == a) continue; if (!IsTerminal(c)) continue; if (next_fork_dist[c] + 1 == next_fork_dist[x] - iter) { Transition(dp[u][i][j], &dp[a][ii][jj]); } } } } } } } } return result; } int main() { scanf("%d", &n); AddArc(0, 1); for (int i = 1; i < n; ++i) { int a, b; scanf("%d%d", &a, &b); AddArc(a, b); } ComputeTraversal(); ComputeNextFork(); printf("%d\n", Solve()); return 0; }