#include #include using namespace std; #include #include using mint = atcoder::modint998244353; int main() { cin.tie(nullptr)->sync_with_stdio(false); int N, K; cin >> N >> K; atcoder::dsu uf(N); vector> to(N); int p = -1, q = -1; for (int e = 0; e < N; ++e) { int a, b; cin >> a >> b; --a, --b; if (!uf.same(a, b)) { uf.merge(a, b); to.at(a).push_back(b); to.at(b).push_back(a); } else { p = a, q = b; } } int v = -1; auto rec = [&](auto &&self, int now, int prv, int d) -> void { for (int nxt : to.at(now)) { if (nxt == prv) continue; if (nxt == q) { v = d + 1; return; } self(self, nxt, now, d + 1); } }; rec(rec, p, -1, 1); mint dp0 = K * mint(K - 1).pow(N - v), dp1 = 0; while (--v) { auto dp0nxt = dp1; dp1 = dp0 * (K - 1) + dp1 * (K - 2); dp0 = dp0nxt; } cout << dp1.val() << endl; }