#include #include #include #include #include #include #include #include #include #include #include "testlib.h" using namespace std; using Graph = vector>; #define MOD 998244353 vector depth; vector subtree_size; vector seen; void dfs(const Graph& G, int v, int p, int d) { seen[v] = true; depth[v] = d; for (auto nv : G[v]) { if (nv == p) continue; dfs(G, nv, v, d + 1); } subtree_size[v] = 1; for (auto c : G[v]) { if (c == p) continue; subtree_size[v] += subtree_size[c]; } } long long modinv(long long a, long long mod) { long long b = mod, u = 1, v = 0; while (b) { long long t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } u %= mod; if (u < 0) u += mod; return u; } int main() { registerValidation(); long long N = inf.readLong((long long)2, (long long)100000); inf.readEoln(); Graph G(N); for (int i = 0; i < N - 1; i++) { int a = inf.readLong((long long)1, N); inf.readSpace(); int b = inf.readLong((long long)1, N); inf.readEoln(); G[a - 1].push_back(b - 1); G[b - 1].push_back(a - 1); } inf.readEof(); depth.assign(N, 0); subtree_size.assign(N, 0); seen.assign(N, false); dfs(G, 0, -1, 0); bool flag = false; for (int i = 0; i < N; i++) if (seen[i] == false) flag = true; if (flag) cout << -1 << endl; long long sum = 0; for (int i = 1; i < N; i++) sum += (N * (N - 1) / 2 - subtree_size[i] * (N - subtree_size[i])) % MOD; sum = sum % MOD * modinv(N * (N - 1) / 2, MOD) % MOD * modinv(N - 1, MOD) % MOD; cout << sum << endl; }