解题思路
- 按照到
的距离远近，进行分层
- 分层步骤：用一个集合记录还未定层的点，用
逐层确定
- 对于当前点
- 与其有连边的（不是删边）且还未确定的点，确定为
的下一层，入队列
- 没连边且还未确定的点，入集合（每次决策建立新集合，用浅拷贝）
- 直到集合为空
- 此时，到
的最优距离确定
- 长度为
的方案数即为答案
- 统计方案数，考虑容斥
- 逐层统计
- 对于当前层，不考虑删边，到该层每一个点的最优距离的方案数（dis+1）为上一层的方案数
- 考虑删边，若
删去，则
的方案不会被统计到
中（不是最优，+1），
- 注意无法到达的点距离为
，需处理
- 最终答案为
- 对于每层的点不会有重复，使用
- 或
(稍慢，因为有排序)
- 防止超时（
太慢）
import java.io.*;
import java.math.BigInteger;
import java.util.*;
//implements Runnable
public class Main {
static long md=(long)998244353;
static long Linf=Long.MAX_VALUE/2;
static int inf=Integer.MAX_VALUE/2;
static int N=200010;
static int n=0;
static int m=0;
static void solve() throws Exception{
AReader input=new AReader();
// String fileName="C:\\Users\\Lenovo\\Downloads\\055.txt";
// Scanner input=new Scanner(new FileReader(fileName));
// BufferedReader input = new BufferedReader(new FileReader(fileName));
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
String al="abcdefghijklmnopqrstuvwxyz";
char[] ac=al.toCharArray();
n=input.nextInt();
m=input.nextInt();
Set<Integer>[] e=new Set[N+1];
for(int i=1;i<=n;++i)e[i]=new HashSet<>();
HashSet<Integer> hs=new HashSet<>();
for(int i=2;i<=n;++i)hs.add(i);
for(int i=1;i<=m;++i){
int u=input.nextInt();
int v=input.nextInt();
e[u].add(v);
e[v].add(u);
}
int[] dis=new int[N+1];
Queue<Integer> q=new LinkedList<>();
q.add(1);
dis[1]=1;
while(!q.isEmpty()){
HashSet<Integer> now=new HashSet<>();
int x=q.poll();
for(int v:hs){
if(!e[x].contains(v)){
dis[v]=dis[x]+1;
q.add(v);
}else{
now.add(v);
}
}
hs=now;
}
if(dis[n]==0){
out.println("-1");
}else{
Set<Integer>[] dep=new HashSet[n+1];
for(int i=0;i<=n;++i)dep[i]=new HashSet<>();
for(int i=1;i<=n;++i){
dep[dis[i]].add(i);
}
long[] f=new long[N+1];
long sum=1;f[1]=1;
for(int i=2;i<=dis[n];++i){
for(int x:dep[i]){
f[x]=sum;
}
for(int x:dep[i-1]){
for(int v:e[x]){
if(dep[i].contains(v)){
f[v]=(f[v]+md-f[x])%md;
}
}
}
sum=0;
for(int x:dep[i]){
sum=(sum+f[x])%md;
}
}
out.println(f[n]);
}
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
solve();
}
// public static final void main(String[] args) throws Exception {
// new Thread(null, new Tx2(), "线程名字", 1 << 27).start();
// }
// @Override
// public void run() {
// try {
// //原本main函数的内容
// solve();
//
// } catch (Exception e) {
// }
// }
static
class AReader{
BufferedReader bf;
StringTokenizer st;
BufferedWriter bw;
public AReader(){
bf=new BufferedReader(new InputStreamReader(System.in));
st=new StringTokenizer("");
bw=new BufferedWriter(new OutputStreamWriter(System.out));
}
public String nextLine() throws IOException{
return bf.readLine();
}
public String next() throws IOException{
while(!st.hasMoreTokens()){
st=new StringTokenizer(bf.readLine());
}
return st.nextToken();
}
public char nextChar() throws IOException{
//确定下一个token只有一个字符的时候再用
return next().charAt(0);
}
public int nextInt() throws IOException{
return Integer.parseInt(next());
}
public long nextLong() throws IOException{
return Long.parseLong(next());
}
public double nextDouble() throws IOException{
return Double.parseDouble(next());
}
public float nextFloat() throws IOException{
return Float.parseFloat(next());
}
public byte nextByte() throws IOException{
return Byte.parseByte(next());
}
public short nextShort() throws IOException{
return Short.parseShort(next());
}
public BigInteger nextBigInteger() throws IOException{
return new BigInteger(next());
}
public void println() throws IOException {
bw.newLine();
}
public void println(int[] arr) throws IOException{
for (int value : arr) {
bw.write(value + " ");
}
println();
}
public void println(int l, int r, int[] arr) throws IOException{
for (int i = l; i <= r; i ++) {
bw.write(arr[i] + " ");
}
println();
}
public void println(int a) throws IOException{
bw.write(String.valueOf(a));
bw.newLine();
}
public void print(int a) throws IOException{
bw.write(String.valueOf(a));
}
public void println(String a) throws IOException{
bw.write(a);
bw.newLine();
}
public void print(String a) throws IOException{
bw.write(a);
}
public void println(long a) throws IOException{
bw.write(String.valueOf(a));
bw.newLine();
}
public void print(long a) throws IOException{
bw.write(String.valueOf(a));
}
public void println(double a) throws IOException{
bw.write(String.valueOf(a));
bw.newLine();
}
public void print(double a) throws IOException{
bw.write(String.valueOf(a));
}
public void print(char a) throws IOException{
bw.write(String.valueOf(a));
}
public void println(char a) throws IOException{
bw.write(String.valueOf(a));
bw.newLine();
}
}
}
