// URL: https://yukicoder.me/problems/no/1507 import std; version(unittest) {} else void main() { int N; io.getV(N); auto g = Graph(N); foreach (_; 0..N-1) { int ui, vi; io.getV(ui, vi); --ui; --vi; g.addEdgeB(ui, vi); } auto a = SList!int(0), b = SList!int(0), visited = new bool[](N); visited[0] = true; while (!a.empty) { auto u = a.front; a.removeFront(); foreach (v; g[u]) { if (!visited[v]) { a.insertFront(v); b.insertFront(v); visited[v] = true; } } } auto t = g.tree(0), c = new int[](N); c[] = 1; while (!b.empty) { auto u = b.front; b.removeFront(); if (u != 0) c[t.parent[u]] += c[u]; } auto r = mint(0); foreach (u; 1..N) { auto d1 = mint(c[0]), d2 = mint(c[u]), d3 = mint(c[0] - c[u]); r += (d3*(d3-1)/2 + d2*(d2-1)/2)/(d1*(d1-1)/2); } io.put(r/(N-1)); } const mod = 998244353; alias mint = ModInt!mod; pure nothrow @safe { T powr(alias pred = "a*b", T, U)(const T a, U n, T one) if (isIntegral!U) { auto b = T(a); alias predFun = binaryFun!pred; if (n == 0) return one; auto r = one; for (; n > 0; n >>= 1) { if (n&1) r = predFun(r, b); b = predFun(b, b); } return r; } T powr(alias pred = "a*b", T, U)(const T a, U n) if (isIntegral!U) { return powr!(pred, T, U)(a, n, T(1)); } } pragma(inline) pure nothrow @nogc @safe { T cdiv(T)(const T a, const T b) { return (a+b-1)/b; } T pmod(T)(const T a, const T b) { return a >= 0 ? a%b : a%b+b; } } pure nothrow @nogc @safe { ExtGcdResult!T extGcd(T)(const T a, const T b) { if (a == 0) { return ExtGcdResult!T(T(b), T(0), T(1)); } else { auto r = extGcd(b%a, a); return ExtGcdResult!T(r.gcd, r.y-(b/a)*r.x, r.x); } } private struct ExtGcdResult(T) { T gcd, x, y; } } struct ModInt(int m) { pragma(inline) pure nothrow @nogc @safe { this(T)(T v) if (isIntegral!T) { i = nm(v); } this(ref return scope const Mint v) { i = v.i; } bool opEquals(T)(T v) const if (isIntegral!T) { return i == v; } bool opEquals(const Mint v) const { return i == v.i; } Mint opUnary(string op: "-")() const { return Mint(-i); } static if (m < int.max/2) { Mint opBinary(string op: "+")(int r) const { Mint m; m.i = nm(i+r); return m; } Mint opBinary(string op: "+")(const Mint r) const { Mint m; m.i = nmp(i+r.i); return m; } ref Mint opOpAssign(string op: "+")(int r) { i = nm(i+r); return this; } ref Mint opOpAssign(string op: "+")(const Mint r) { i = nmp(i+r.i); return this; } } else { Mint opBinary(string op: "+")(int r) const { Mint m; m.i = nm(l+r); return m; } Mint opBinary(string op: "+")(const Mint r) const { Mint m; m.i = nmp(l+r.i); return m; } ref Mint opOpAssign(string op: "+")(int r) { i = nm(l+r); return this; } ref Mint opOpAssign(string op: "+")(const Mint r) { i = nmp(l+r.i); return this; } } Mint opBinary(string op: "-")(int r) const { return Mint(i-r); } Mint opBinary(string op: "-")(const Mint r) const { return Mint(i-r.i); } ref Mint opOpAssign(string op: "-")(int r) { i = nm(i-r); return this; } ref Mint opOpAssign(string op: "-")(const Mint r) { i = nm(i-r.i); return this; } Mint opBinary(string op, T)(T r) const if ((op == "+" || op == "-") && isIntegral!T && !is(T == int)) { return Mint(mixin("l"~op~"r")); } ref Mint opOpAssign(string op, T)(T r) if ((op == "+" || op == "-") && isIntegral!T && !is(T == int)) { i = nm(mixin("l"~op~"r")); return this; } Mint opBinary(string op: "*", T)(T r) const if (isIntegral!T) { Mint m; m.i = nm(l*r); return m; } Mint opBinary(string op: "*")(const Mint r) const { Mint m; m.i = nmp(l*r.i); return m; } ref Mint opOpAssign(string op: "*", T)(T r) if (isIntegral!T) { i = nm(l*r); return this; } ref Mint opOpAssign(string op: "*")(const Mint r) { i = nmp(l*r.i); return this; } ref Mint opUnary(string op: "++")() { i = nmp(i+1); return this; } ref Mint opUnary(string op: "--")() { i = nm(i-1); return this; } Mint opBinary(string op: "^^", T)(T n) if (isIntegral!T) { return powr(this, n, Mint(1)); } Mint opBinary(string op: "/")(const Mint r) const { return Mint(l*r.inv.i); } ref Mint opOpAssign(string op: "/")(const Mint r) { i = nm(l*r.inv.i); return this; } Mint opBinary(string op: "/", T)(T r) const if (isIntegral!T) { return opBinary!op(Mint(r)); } ref Mint opOpAssign(string op: "/", T)(T r) if (isIntegral!T) { return opOpAssign!op(Mint(r)); } Mint inv() const { return Mint(extGcd(i, m).x); } } pure nothrow @nogc @safe { ref Mint opAssign(T)(T v) if (isIntegral!T) { i = nm(v); return this; } ref Mint opAssign(const Mint v) { i = v.i; return this; } } pure nothrow @safe { string toString() const { return i.to!string; } } private { alias Mint = ModInt!m; version(BigEndian) union { long l; struct { int i2; int i; } } else union { long l; int i; } pragma(inline) pure nothrow @nogc @safe { int nm(T)(T v) const if (isIntegral!T) { return cast(int)pmod(v, m); } int nmp(T)(T v) const if (isIntegral!T) { return cast(int)(v%m); } } } } struct Graph { alias Node = int; Node n; Node[][] g; alias g this; pure nothrow @safe { this(Node n) { this.n = n; g = new Node[][](n); } void addEdge(Node u, Node v) in { assert(0 <= u && u < n && 0 <= v && v < n); } do { g[u] ~= v; } void addEdgeB(Node u, Node v) in { assert(0 <= u && u < n && 0 <= v && v < n); } do { g[u] ~= v; g[v] ~= u; } } } struct GraphW(W = int, W i = 10^^9) { alias Node = int, Wt = W, inf = i; struct Edge { Node src, dst; Wt wt; alias cap = wt; } Node n; Edge[][] g; alias g this; pure nothrow @safe { this(Node n) { this.n = n; g = new Edge[][](n); } void addEdge(Node u, Node v, Wt w) in { assert(0 <= u && u < n && 0 <= v && v < n); } do { g[u] ~= Edge(u, v, w); } void addEdgeB(Node u, Node v, Wt w) in { assert(0 <= u && u < n && 0 <= v && v < n); } do { g[u] ~= Edge(u, v, w); g[v] ~= Edge(v, u, w); } } } struct GraphM(W = int, W i = 10^^9) { alias Node = int, Wt = W, inf = i; Node n; Wt[][] g; alias g this; pure nothrow @safe { this(int n) { this.n = n; g = new Wt[][](n, n); } static GraphM!(W, i) init(Node n) { auto g = GraphM!(W, i)(n); foreach (i; 0..n) { g[i][] = inf; g[i][i] = 0; } return g; } } } struct Tree(Graph) { alias Node = Graph.Node; Graph g; alias g this; Node root; Node[] parent, dfsOrder; int[] size, depth; pure nothrow @safe { this(Graph g, Node r) in { assert(0 <= r && r < g.n); } do { this.g = g; this.root = r; parent = new Node[](n); depth = new int[](n); depth[] = -1; auto st = SList!UP(UP(r, r)); while (!st.empty) { auto up = st.front; st.removeFront(); parent[up.u] = up.p; depth[up.u] = depth[up.p] + 1; dfsOrder ~= up.u; foreach (v; g[up.u]) if (v != up.p) st.insertFront(UP(v, up.u)); } size = new int[](n); size[] = 1; foreach_reverse (u; dfsOrder.drop(1)) size[parent[u]] += size[u]; } auto children(Node u) const in { assert(0 <= u && u < g.n); } do { return g[u].filter!(v => v != parent[u]); } } private { struct UP { Node u, p; } } } pure nothrow @safe { auto tree(Graph, Node)(Graph g, Node r) in { assert(0 <= r && r < g.n); } do { return Tree!Graph(g, r); } } auto io = IO!()(); struct IO(alias IN = stdin, alias OUT = stdout) { import core.stdc.stdlib : exit; void getV(T...)(ref T v) { foreach (ref w; v) get(w); } void getA(T)(size_t n, ref T v) if (hasAssignableElements!T) { v = new T(n); foreach (ref w; v) get(w); } void getC(T...)(size_t n, ref T v) if (allSatisfy!(hasAssignableElements, T)) { foreach (ref w; v) w = new typeof(w)(n); foreach (i; 0..n) foreach (ref w; v) get(w[i]); } void getM(T)(size_t r, size_t c, ref T v) if (hasAssignableElements!T && hasAssignableElements!(ElementType!T)) { v = new T(r); foreach (ref w; v) getA(c, w); } template getS(E...) { void getS(T)(size_t n, ref T v) { v = new T(n); foreach (ref w; v) foreach (e; E) mixin("get(w."~e~");"); } } const struct PutConf { bool newline = true, flush, exit; string floatFormat = "%.10f", delimiter = " "; } void put(alias conf = "{}", T...)(T v) { putMain!conf(v); } void putB(alias conf = "{}", S, T)(bool c, S t, T f) { if (c) put!conf(t); else put!conf(f); } void putRaw(T...)(T v) { OUT.write(v); OUT.writeln; } private { dchar[] buf; auto sp = (new dchar[](0)).splitter; void nextLine() { IN.readln(buf); sp = buf.splitter; } void get(T)(ref T v) { if (sp.empty) nextLine(); v = sp.front.to!T; sp.popFront(); } void putMain(alias conf, T...)(T v) { mixin("const PutConf c = "~conf~";"); foreach (i, w; v) { putOne!conf(w); if (i+1 < v.length) OUT.write(c.delimiter); } static if (c.newline) OUT.writeln; static if (c.flush) OUT.flush(); static if (c.exit) exit(0); } void putOne(alias conf, T)(T v) { mixin("const PutConf c = "~conf~";"); static if (isInputRange!T && !isSomeString!T) putRange!conf(v); else static if (isFloatingPoint!T) OUT.write(format(c.floatFormat, v)); else static if (hasMember!(T, "fprint")) v.fprint(OUT); else OUT.write(v); } void putRange(alias conf, T)(T v) { mixin("const PutConf c = "~conf~";"); auto w = v; while (!w.empty) { putOne!conf(w.front); w.popFront(); if (!w.empty) OUT.write(c.delimiter); } } } }