7586: Jumping on a Cactus
内存限制：128 MB
时间限制：1 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：0
通过：0
题目描述
It is preferrable to read the pdf statment.
Cuber QQ has recently learned jumping on graphs. He now wants to demonstrate his skills on a cactus.
Recall that, cactus refers to a graph with every edge appearing in at most one cycle. If you do not know what a cycle is, formally, a cycle of length k denotes an edge sequence (u1,u2),(u2,u3),…,(uk−1,uk),(uk,u1).
Assuming you are given an undirected cactus G=(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, p1,p2,…,pn, and they are visited in order.
Cuber 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,
Count the number of different monotonic jumping plans. Since the answer can be very large, you should print the answer modulo 998 244 353.
Cuber QQ has recently learned jumping on graphs. He now wants to demonstrate his skills on a cactus.
Recall that, cactus refers to a graph with every edge appearing in at most one cycle. If you do not know what a cycle is, formally, a cycle of length k denotes an edge sequence (u1,u2),(u2,u3),…,(uk−1,uk),(uk,u1).
Assuming you are given an undirected cactus G=(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, p1,p2,…,pn, and they are visited in order.
Cuber 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,
- for all edges (u,v)∈E, d(u,e)<d(v,e) when u is visited before v, or,
- for all edges (u,v)∈E, d(u,e)>d(v,e) when u is visited after v.
Count the number of different monotonic jumping plans. Since the answer can be very large, you should print the answer modulo 998 244 353.
输入格式
The first line of the input contains a single integer T (1≤T≤30), denoting the number of test cases.
For each of the next T cases:
There are at most 10 test cases where n≥1 000.
For each of the next T cases:
- The first line contains three space-separated integers n, m, e (2≤n≤5 000, 1≤m≤2(n−1), 1≤e≤n).
- The i-th of the next m lines contains two space-separated integers ui, vi (1≤ui,vi≤n, ui≠vi). It is guaranteed that d(ui,e)≠d(vi,e).
There are at most 10 test cases where n≥1 000.
输出格式
For each test case, output one line contains one integer denoting the answer modulo 998 244 353.
For the example, G looks like:
3 is the index of reference vertex.
There are 8 correct permutations:
Notes
For the example, G looks like:
3 is the index of reference vertex.
There are 8 correct permutations:
- {3,2,4,1,6,5}.
- {3,2,1,4,6,5}.
- {3,2,1,6,4,5}.
- {3,2,1,6,5,4}.
- {3,2,4,6,1,5}.
- {3,2,6,4,1,5}.
- {3,2,6,1,4,5}.
- {3,2,6,1,5,4}.
输入样例 复制
1
6 7 3
6 2
5 6
1 5
1 2
3 2
3 2
4 2输出样例 复制
8