P8867 [NOIP2022] Building Military Camps

Countries A and B are at war, and country A plans to build some military camps on its own territory. Country A’s territory consists of $n$ cities, connected by $m$ bidirectional roads, such that any two cities are directly or indirectly reachable through the roads. Country A will choose one or more cities (at least one) and build exactly one military camp in each chosen city. It is well known that communication between camps is crucial. However, country A has received intelligence that country B will soon attack one of A’s roads, but the exact target is unknown. If B’s attack succeeds, that road will be cut, which may cause some two camps in A to be unable to reach each other, something A is keen to avoid. Therefore, A decides to station troops to guard some roads (it could be one or more, or possibly none). Country A is confident that any guarded road can withstand B’s attack and will not be cut. Country A wants to design a plan for building camps and guarding roads such that, no matter which road in A is attacked by B, it will not cause any two camps to be unable to reach each other. Please help country A calculate how many possible plans there are for building camps and guarding roads. Since the number of plans may be large, output the value modulo $1,000,000,007\left(10^{9}+7\right)$. Two plans are considered different if and only if there exists at least one city that has a camp in one plan but not in the other, or there exists at least one road that is guarded in one plan but not in the other.

The first line contains two positive integers $n, m$, denoting the number of cities and the number of bidirectional roads, respectively. The next $m$ lines each contain two positive integers $u_i, v_i$, describing a bidirectional road connecting $u_i$ and $v_i$. There are no multiple edges or self-loops.

Output one line containing an integer, the number of valid plans for building camps and guarding roads, modulo $1,000,000,007\left(10^{9}+ 7\right)$.

### Sample 1 Explanation In the sample, country A has two cities, with $1$ road connecting them. All possible plans are as follows: - Build a camp in city $1$, do not guard the road. - Build a camp in city $1$, guard the road. - Build a camp in city $2$, do not guard the road. - Build a camp in city $2$, guard the road. - Build camps in cities $1, 2$, guard the road. ### Constraints For all testdata, it is guaranteed that $1 \leq n \leq 5 \times 10^5$, $n - 1 \leq m \leq 10^6$, $1 \leq u_i, v_i \leq n$, $u_i \neq v_i$. | Test point ID | $n \leq$ | $m \leq$ | Special condition | | :-: | :-: | :-: | :-: | | $1 \sim 3$ | $8$ | $10$ | None | | $4 \sim 7$ | $16$ | $25$ | ^ | | $8 \sim 9$ | $3000$ | $5000$ | ^ | | $10 \sim 11$ | $5 \times 10^5$ | $10^6$ | Special property $\mathrm{A}$ | | $12 \sim 14$ | ^ | ^ | $m = n - 1$ | | $15 \sim 16$ | ^ | ^ | $m = n$ | | $17 \sim 20$ | ^ | ^ | None | Special property $\mathrm{A}$: guarantee $m = n - 1$ and the $i$-th road connects city $i$ and $i + 1$. Translated by ChatGPT 5