4314. 拼好题

【题目背景】

题如其名

【题目描述】

给定一个 $n$ 个点 $m$ 条边的图 $G=(V,E)$，求：

1.多少 $E'\subseteq E$，满足 $G'=(V,E')$ 是一个连通图。

2.多少 $E'\subseteq E$，满足 $G'=(V,E')$ 是一个连通二分图。

3. 给每一条无向边定向得到 $G'$，使得 $G'$ 是一个 DAG。

答案对 $10^9+7$ 取模。

【输入格式】

第一行两个整数 $n,m$。

接下来 $m$ 行，每行两个整数 $u,v$，表示 $G$ 中的一条边。

【输出格式】

三行三个整数，第 $i$ 行表示第 $i$ 个问题的答案。

【样例输入】

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

【样例输出】

4
3
24

【数据规模与约定】

$n\le 15,m\le \frac{n(n-1)}{2}$