通道（passageway）

题目描述

$\text{Alpha}$ 和 $\text{Beta}$ 生活在两个平行世界，两个世界都有 $n$ 个点。最开始 $\text{Alpha}$ 的世界会有 $m ∈ [0, n)$ 条双向边，$\text{Beta}$ 的世界有 $n-1-m$ 条双向边，两个世界都满足任意两个点可以互相到达的点有且仅有一条道路。

$\text{Alpha}$ 梦想着与 $\text{Beta}$ 环游世界，所以他会在两个世界之间修建 $n$ 条通道，即 $n$ 条双向边。具体地，$\text{Alpha}$ 会选择一个排列，并对$\text{Alpha}$ 世界的第 $i$ 个点和 $\text{Beta}$ 世界的第 $p_i$ 个点连一条双向边。

$\text{Alpha}$ 想知道有多少种可能的排列，使得连边后两个世界联通，即 $2n$ 个点中任意两个点可以互相到达。

输入格式

第一行两个数 $n, m$，接下来的 $n -1$ 行，每行两个数 $u, v$ 表示一条边，前 $m$ 行表示的是$\text{Alpha}$ 世界的边，后 $n-m -1$ 表示的 $\text{Beta}$ 世界的边。

输出格式

一个整数表示答案，答案对 $998244353$ 取模。

样例1

输入样例

10 1
2 3
2 8
1 2
3 4
3 9
2 6
2 5
6 7
1 10

输出样例

1693440

样例2

见下发样例

数据范围

• 子任务1 (10分)：$n≤ 10$。

• 子任务2 (10分)：$n≤15$。

• 子任务3 (10分)：$n ≤20$。

• 子任务4 (10分)：$n ≤30$。

• 子任务5 (10分)：$n ≤50$。

• 子任务6 (20分)：$n ≤10^3$。

• 子任务7 (30分)：$n ≤10^6$。

对于所有数据，保证 $n≤ 10^6$，给定的图满足题目描述。