#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=1e5+9,P=998244353;
int qmi(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=(LL)res*a%P;
        a=(LL)a*a%P;
        b>>=1;
    }
    return res;
}
int n,k,x,y; bool on[N];
vector<int> g[N]; int deg[N];
int q[N],hh,tt=-1;
int ch[N],len;
int f[N][3][2],tmp[3][2];
int res;
int pre[N][2],suf[N][2];
void dfs(int u,int p){
    f[u][0][0]=f[u][0][1]=1;
    for(int &v:g[u]){
        if(v==p||on[v]) continue;
        dfs(v,u);
        memcpy(tmp,f[u],sizeof(tmp));
        for(int x1:{0,1,2}) for(int y1:{0,1}) for(int x2:{0,1,2}) for(int y2:{0,1}) if(!y1||!y2){
            f[u][min(x1+1,2)][y1+y2]=(f[u][min(x1+1,2)][y1+y2]+(LL)tmp[x1][y1]*f[v][x2][y2]%P*(x2?y:x))%P;
        } 
    }
    for(int x1:{0,1,2}) res=(res+(LL)f[u][x1][1]*(x1>=2?y:x))%P;
    // printf("dfs %d %d: ",u,res);
    // for(int x1:{0,1,2}) for(int y1:{0,1}) printf("%d ",f[u][x1][y1]); puts("");
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1,a,b;i<=n;i++) scanf("%d%d",&a,&b),g[a].push_back(b),g[b].push_back(a),deg[a]++,deg[b]++;
    for(int i=1;i<=n;i++){
        on[i]=1;
        if(deg[i]==1) q[++tt]=i;
    }
    while(hh<=tt){
        int u=q[hh++];
        on[u]=0;
        for(int &v:g[u]) if(--deg[v]==1) q[++tt]=v;
    }
    y=qmi(1-k+P,P-2),x=(LL)k*y%P;
    for(int i=1;i<=n;i++) if(on[i]){
        int x=i;
        do{
            ch[++len]=x;
            for(int &u:g[x]) if(on[u]&&u!=ch[len-1]){
                x=u;
                break;
            }
        }while(x^i);
        break;
    }
    for(int i=1;i<=n;i++) if(on[i]) dfs(i,0);
    for(int i=1,pre[2]={0,0};i<=len;i++){
        int sm[2][2]={0,0};
        for(int x1:{0,1,2}) for(int y1:{0,1}) sm[!!x1][y1]=(sm[!!x1][y1]+f[ch[i]][x1][y1])%P;
        int tmp[2]={0,0},co[2]={0,0};
        for(int x1:{0,1}) for(int y1:{0,1}) tmp[y1]=(tmp[y1]+(LL)sm[x1][y1]*(x1?y:x))%P,co[y1]=(co[y1]+(LL)sm[x1][y1]*y)%P;
        res=(res+(LL)pre[0]*tmp[1]+(LL)pre[1]*tmp[0])%P;
        int p0=pre[0],p1=pre[1];
        pre[0]=(tmp[0]+(LL)p0*co[0])%P;
        pre[1]=(tmp[1]+(LL)p1*co[0]+(LL)p0*co[1])%P;
    }
    // printf("%d\n",res);
    for(int i=1,mul[2]={1,0};i<=len;i++){
        int sm[2][2]={0,0};
        for(int x1:{0,1,2}) for(int y1:{0,1}) sm[!!x1][y1]=(sm[!!x1][y1]+f[ch[i]][x1][y1])%P;
        int tmp[2]={0,0},co[2]={0,0};
        for(int x1:{0,1}) for(int y1:{0,1}) tmp[y1]=(tmp[y1]+(LL)sm[x1][y1]*(x1?y:x))%P,co[y1]=(co[y1]+(LL)sm[x1][y1]*y)%P;
        pre[i][0]=(LL)mul[0]*tmp[0]%P;
        pre[i][1]=((LL)mul[0]*tmp[1]+(LL)mul[1]*tmp[0])%P;
        int m0=mul[0],m1=mul[1];
        mul[0]=(LL)m0*co[0]%P;
        mul[1]=((LL)m1*co[0]+(LL)m0*co[1])%P;
        // printf("pre %d %d %d %d %d %d %d %d %d\n",ch[i],tmp[0],tmp[1],pre[i][0],pre[i][1],mul[0],mul[1],co[0],co[1]);
    }
    for(int i=len,mul[2]={1,0};i;i--){
        int sm[2][2]={0,0};
        for(int x1:{0,1,2}) for(int y1:{0,1}) sm[!!x1][y1]=(sm[!!x1][y1]+f[ch[i]][x1][y1])%P;
        int tmp[2]={0,0},co[2]={0,0};
        for(int x1:{0,1}) for(int y1:{0,1}) tmp[y1]=(tmp[y1]+(LL)sm[x1][y1]*(x1?y:x))%P,co[y1]=(co[y1]+(LL)sm[x1][y1]*y)%P;
        suf[i][0]=(LL)mul[0]*tmp[0]%P;
        suf[i][1]=((LL)mul[0]*tmp[1]+(LL)mul[1]*tmp[0])%P;
        int m0=mul[0],m1=mul[1];
        mul[0]=(LL)m0*co[0]%P;
        mul[1]=((LL)m1*co[0]+(LL)m0*co[1])%P;
        // printf("suf %d %d %d %d %d %d %d %d %d\n",ch[i],tmp[0],tmp[1],suf[i][0],suf[i][1],mul[0],mul[1],co[0],co[1]);
    }
    for(int i=len;i;i--) for(int o:{0,1}) suf[i][o]=(suf[i][o]+suf[i+1][o])%P;
    for(int i=1;i<len;i++) res=(res+(LL)pre[i][0]*suf[i+1][1]+(LL)pre[i][1]*suf[i+1][0])%P;
    // printf("%d\n",res);
    int mul[2]={1,0};
    for(int i=1;i<=len;i++){
        int sm[2]={0,0};
        for(int x1:{0,1,2}) for(int y1:{0,1}) sm[y1]=(sm[y1]+(LL)f[ch[i]][x1][y1]*y)%P;
        int m0=mul[0],m1=mul[1];
        mul[0]=(LL)m0*sm[0]%P;
        mul[1]=((LL)m0*sm[1]+(LL)m1*sm[0])%P;
        // printf("--%d %d %d %d %d\n",ch[i],sm[0],sm[1],mul[0],mul[1]);
    }
    res=(res+mul[1])%P;
    // printf("%d\n",res);
    res=(LL)res*qmi(1-k+P,n)%P;
    printf("%d\n",res);
    return 0;
}