{"problem":{"name":"Safety Journey","description":{"content":"The Republic of AtCoder has $N$ cities, called City $1$, City $2$, $\\ldots$, City $N$. Initially, there was a bidirectional road between every pair of different cities, but $M$ of these roads have bec","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc212_e"},"statements":[{"statement_type":"Markdown","content":"The Republic of AtCoder has $N$ cities, called City $1$, City $2$, $\\ldots$, City $N$. Initially, there was a bidirectional road between every pair of different cities, but $M$ of these roads have become unusable due to deterioration over time. More specifically, for each $1\\leq i \\leq M$, the road connecting City $U_i$ and City $V_i$ has become unusable.\nTakahashi will go for a $K$\\-day trip that starts and ends in City $1$. Formally speaking, a $K$\\-day trip that starts and ends in City $1$ is a sequence of $K+1$ cities $(A_0, A_1, \\ldots, A_K)$ such that $A_0=A_K=1$ holds and for each $0\\leq i\\leq K-1$, $A_i$ and $A_{i+1}$ are different and there is still a usable road connecting City $A_i$ and City $A_{i+1}$.\nPrint the number of different $K$\\-day trips that start and end in City $1$, modulo $998244353$. Here, two $K$\\-day trips $(A_0, A_1, \\ldots, A_K)$ and $(B_0, B_1, \\ldots, B_K)$ are said to be different when there exists an $i$ such that $A_i\\neq B_i$.\n\n## Constraints\n\n*   $2 \\leq N \\leq 5000$\n*   $0 \\leq M \\leq \\min\\left( \\frac{N(N-1)}{2},5000 \\right)$\n*   $2 \\leq K \\leq 5000$\n*   $1 \\leq U_i<V_i \\leq N$\n*   All pairs $(U_i, V_i)$ are pairwise distinct.\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$ $K$\n$U_1$ $V_1$\n$:$\n$U_M$ $V_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc212_e","tags":[],"sample_group":[["3 1 4\n2 3","4\n\nThere are four different trips as follows.\n\n*   ($1,2,1,2,1$)\n*   ($1,2,1,3,1$)\n*   ($1,3,1,2,1$)\n*   ($1,3,1,3,1$)\n\nNo other trip is valid, so we should print $4$."],["3 3 3\n1 2\n1 3\n2 3","0\n\nNo road remains usable, so there is no valid trip."],["5 3 100\n1 2\n4 5\n2 3","428417047"]],"created_at":"2026-03-03 11:01:13"}}