{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e\u003cb\u003eIt is preferrable to read the pdf statment.\u003c/b\u003e\u003cbr\u003e\u003cbr\u003eCuber QQ has recently learned jumping on graphs. He now wants to demonstrate his skills on a \u003ci\u003ecactus\u003c/i\u003e.\u003cbr\u003e\u003cbr\u003eRecall that, \u003ci\u003ecactus\u003c/i\u003e refers to a graph with every edge appearing in \u003cb\u003eat most one\u003c/b\u003e \u003ci\u003ecycle\u003c/i\u003e. If you do not know what a \u003ci\u003ecycle\u003c/i\u003e is, formally, a \u003ci\u003ecycle\u003c/i\u003e of length $k$ denotes an edge sequence $(u_1,u_2), (u_2,u_3),\\ldots,(u_{k-1},u_k),(u_k,u_1)$.\u003cbr\u003e\u003cbr\u003eAssuming you are given an undirected cactus $G\u003d(V, E)$, with $n$ vertices and $m$ edges. A jumping on the cactus can be thought of as a visit to all vertices where every vertex is visited exactly once. That can be represented with a permutation of $1$ to $n$, $p_1, p_2, \\ldots, p_n$, and they are visited in order.\u003cbr\u003e\u003cbr\u003eCuber QQ also wishes his jumping to be gradually approaching or distancing away from a particular node $e$. Concretely, we define $d(a, b)$ to be the distance from $a$ to $b$ (the minimum edges needs to be passed through from $a$ to $b$). A jumping is defined to be monotonic if,\u003cbr\u003e\u003cbr\u003e\u003cul\u003e\u003cbr\u003e\u003cli\u003e for all edges $(u, v) \\in E$, $d(u, e) \u0026lt; d(v, e)$ when $u$ is visited before $v$, or,\u003c/li\u003e\u003cbr\u003e\u003cli\u003e for all edges $(u, v) \\in E$, $d(u, e) \u0026gt; d(v, e)$ when $u$ is visited after $v$.\u003c/li\u003e\u003cbr\u003e\u003c/ul\u003e\u003cbr\u003e\u003cbr\u003eCount the number of different monotonic jumping plans. Since the answer can be very large, you should print the answer modulo $998~244~353$.\u003cbr\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line of the input contains a single integer $T$ ($1\\le T\\le 30$), denoting the number of test cases.\u003cbr\u003e\u003cbr\u003eFor each of the next $T$ cases:\u003cbr\u003e\u003cbr\u003e\u003cul\u003e\u003cbr\u003e\u003cli\u003e The first line contains three space-separated integers $n$, $m$, $e$ ($2\\le n\\le 5~000$, $1\\le m\\le 2(n-1)$, $1\\le e\\le n$).\u003c/li\u003e\u003cbr\u003e\u003cli\u003e The $i$-th of the next $m$ lines contains two space-separated integers $u_i$, $v_i$ ($1\\le u_i,v_i\\le n$, $u_i\\ne v_i$). It is guaranteed that $d(u_i, e) \\ne d(v_i, e)$.\u003c/li\u003e\u003cbr\u003e\u003c/ul\u003e\u003cbr\u003e\u003cbr\u003eThere are at most $10$ test cases where $n\\ge 1~000$."}},{"title":"Output","value":{"format":"HTML","content":"For each test case, output one line contains one integer denoting the answer modulo $998~244~353$.\u003cbr\u003e\u003cbr\u003e\u003ch3\u003eNotes\u003c/h3\u003e\u003cbr\u003eFor the example, $G$ looks like:\u003cbr\u003e\u003cbr\u003e\u003ccenter\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/284556f9029bc83ca076828e73407e92?v\u003d1726361733\"\u003e\u003c/center\u003e\u003cbr\u003e\u003cbr\u003e$3$ is the index of reference vertex.\u003cbr\u003e\u003cbr\u003eThere are $8$ correct permutations:\u003cbr\u003e\u003cbr\u003e\u003cul\u003e\u003cbr\u003e\u003cli\u003e $\\{ 3,2,4,1,6,5 \\}$.\u003c/li\u003e\u003cbr\u003e\u003cli\u003e $\\{ 3,2,1,4,6,5 \\}$.\u003c/li\u003e\u003cbr\u003e\u003cli\u003e $\\{ 3,2,1,6,4,5 \\}$.\u003c/li\u003e\u003cbr\u003e\u003cli\u003e $\\{ 3,2,1,6,5,4 \\}$.\u003c/li\u003e\u003cbr\u003e\u003cli\u003e $\\{ 3,2,4,6,1,5 \\}$.\u003c/li\u003e\u003cbr\u003e\u003cli\u003e $\\{ 3,2,6,4,1,5 \\}$.\u003c/li\u003e\u003cbr\u003e\u003cli\u003e $\\{ 3,2,6,1,4,5 \\}$.\u003c/li\u003e\u003cbr\u003e\u003cli\u003e $\\{ 3,2,6,1,5,4 \\}$.\u003c/li\u003e\u003cbr\u003e\u003c/ul\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n6 7 3\r\n6 2\r\n5 6\r\n1 5\r\n1 2\r\n3 2\r\n3 2\r\n4 2\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e8\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}