#1753. 杏仁

    ID: 1753 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1092来源:qoj.ac数据:公开样例深搜

杏仁

杏仁

题目描述

标题: 杏仁 - Problem - QOJ.ac

Statistics

The problem was used in the following contests:

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

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

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

回答 q 次询问,每次询问给出一个点 u(u≠s),求 G 有多少张【杏仁子图】G′,满足在 G′ 中有 s→u 的边。答案对 998244353 取模。

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

  1. E′⊆E;
  2. u∈V′,当且仅当存在 v 使得 E′ 中有 u→v 或 v→u 的边;
  3. s,t∈V′,且 G′ 是【杏仁】。

输入格式

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

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

接下来 m 行,每行包含两个整数 u 和 v,表示 G 中一条 u→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≤n≤22,0≤m≤10000,0≤q≤n。

子任务 1(10 分):n≤11,m≤20;

子任务 2(10 分):n≤11;

子任务 3(15 分):n≤17;

子任务 4(10 分):m=n2,每条有向边 u→v 恰好出现一次;

子任务 5(15 分):n≤20;

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

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

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

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