QOJ.ac

QOJ

Time Limit: 6 s Memory Limit: 512 MB Total points: 100

# 5411. 杏仁

Statistics

对于给定的源点 $s$、汇点 $t$,一张有向图被称为【杏仁】,当且仅当:

  1. 从 $s$ 点出发,可以到达所有点;
  2. $s$ 点的入度为 $0$;
  3. $t$ 点的出度为 $0$;
  4. 除 $s, t$ 点外,每个点的入度、出度都为 $1$。

给定一张 $n$ 个点,$m$ 条边的有向图 $G$,点从 $1$ 到 $n$ 编号,给定 $s$ 和 $t$ 的编号($s \ne t$)。

回答 $q$ 次询问,每次询问给出一个点 $u$($u \ne s$),求 $G$ 有多少张【杏仁子图】$G'$,满足在 $G'$ 中有 $s\to u$ 的边。答案对 $998\,244\,353$ 取模。

其中,设 $G=(V, E)$,$G'=(V', E')$ 称为 $G$ 的一个【杏仁子图】,当且仅当:

  1. $E' \subseteq E$;
  2. $u \in V'$,当且仅当存在 $v$ 使得 $E'$ 中有 $u\to v$ 或 $v\to u$ 的边;
  3. $s, t \in V'$,且 $G'$ 是【杏仁】。

输入格式

输入第一行包含两个整数 $n$ 和 $m$;

接下来一行包含两个整数,分别表示 $s$ 和 $t$ 的编号。

接下来 $m$ 行,每行包含两个整数 $u$ 和 $v$,表示 $G$ 中一条 $u\to v$ 的边。

接下来一行包含一个整数 $q$。

接下来 $q$ 行,每行包含一个整数,表示一次询问中 $u$ 点的编号。

输出格式

对于每次询问,输出一行一个整数,表示答案。

样例数据

样例输入

5 10
1 5
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
4
2
3
4
5

样例输出

20
14
10
15

数据范围

对于全部数据,$2 \le n \le 22$,$0 \le m \le 10\,000$,$0 \le q \le n$。

子任务 1($10$ 分):$n \le 11$,$m \le 20$;

子任务 2($10$ 分):$n \le 11$;

子任务 3($15$ 分):$n \le 17$;

子任务 4($10$ 分):$m=n^2$,每条有向边 $u\to v$ 恰好出现一次;

子任务 5($15$ 分):$n \le 20$;

子任务 6($15$ 分):$q=1$;

子任务 7($25$ 分):无特殊限制。