{"problem":{"name":"Sliding Puzzle On Tree","description":{"content":"You are given a tree with $N$ vertices numbered $1$ to $N$. The $i$\\-th edge of the tree connects vertices $u_i$ and $v_i$. For each $K=1, 2, \\ldots, N$, solve the following problem: > There are $K$ ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc066_e"},"statements":[{"statement_type":"Markdown","content":"You are given a tree with $N$ vertices numbered $1$ to $N$. The $i$\\-th edge of the tree connects vertices $u_i$ and $v_i$.\nFor each $K=1, 2, \\ldots, N$, solve the following problem:\n\n> There are $K$ stones numbered $1, 2, \\ldots, K$, with the stone numbered $i$ placed on vertex $i$. You can repeatedly perform the following operation:\n> \n> *   Choose two vertices $u$ and $v$ connected by an edge such that $u$ has a stone on it and $v$ does not. Move the stone from $u$ to $v$.\n> \n> Find the number, modulo $998244353$, of possible configurations of the stones after performing the operations. Two configurations are distinguished if and only if there is a stone whose position differs between those configurations.\n\n$T$ test cases are given; solve each of them.\n\n## Constraints\n\n*   $1\\leq T\\leq 10^5$\n*   $1\\leq N\\leq 2\\times 10^5$\n*   $1\\leq u_i, v_i\\leq N$\n*   The given graph is a tree.\n*   The sum of $N$ over all test cases in a single input is at most $2\\times 10^5$.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$T$\n$\\text{case}_1$\n$\\vdots$\n$\\text{case}_T$\n\nEach test case is given in the following format:\n\n$N$\n$u_1$ $v_1$\n$\\vdots$\n$u_{N-1}$ $v_{N-1}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc066_e","tags":[],"sample_group":[["1\n4\n1 2\n1 3\n1 4","4 12 4 1\n\nLet us represent the configuration of stones by the sequence of vertices where the stones numbered $1, 2, \\ldots, K$ are placed.\n\n*   For $K=1$, there are $4$ possible configurations: $(1), (2), (3), (4)$.\n*   For $K=2$, there are $12$ possible configurations: $(1,2), (1,3), (1,4), (2,1), (2,3), (2,4), (3,1), (3,2), (3,4), (4,1), (4,2), (4,3)$.\n*   For $K=3$, there are $4$ possible configurations: $(1,2,3), (4,1,3), (4,2,1), (4,2,3)$.\n*   For $K=4$, there is $1$ possible configuration: $(1,2,3,4)$.\n\nFor $K=3$, refer to the following figure.\n![image](https://img.atcoder.jp/agc066/f2dc57ae01aa4f1ccb51c1a2b8fe7d15.png)"],["4\n1\n5\n1 4\n5 2\n3 4\n2 1\n7\n1 7\n2 7\n5 6\n4 1\n1 6\n3 6\n10\n1 2\n2 3\n3 4\n4 5\n5 6\n2 7\n3 8\n4 9\n5 10","1\n5 10 10 5 1\n7 42 210 840 84 7 1\n10 90 720 5040 30240 151200 604800 720 10 1\n\nThe tree given in each test case is as follows:\n![image](https://img.atcoder.jp/agc066/744a8d907603331334518cc5d7b62bb9.png)"]],"created_at":"2026-03-03 11:01:14"}}