NOIP '22 P3 - Facility Construction

View as PDF

Submit solution

Points: 17 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem types

Country A and Country B are at war, and Country A intends to build some facilities.

The territory of country A is composed of n cities, and m two-way roads connect these cities, so that any two cities can be directly or indirectly reached by road. Country A intends to choose one or more cities (at least one) and build a facility at each of these cities.

Communications between facilities are very important. However, country B will likely attack a road of country A in the near future, but the specific target of the attack is unknown. If this attack is successful, this road will be cut off, which may cause two facilities in country A to be unable to reach each other, which country A tries to avoid. Therefore, country A decides to send troops to guard several roads (it can be one or more, or none of them). Country A is confident that the roads guarded by troops can resist the attack of country B and not be cut off.

Country A hopes to formulate a plan for building facilities and guarding roads, so that no matter which road of country A is attacked by country B, all facilities will remain reachable from each other. Now, please help country A calculate the total number of possible plans for building facilities and guarding roads. Since the number of schemes may be large, you only need to output its value modulo 10^{9}+7. Two proposals are considered different if and only if there exists at least one city that has a facility built in one proposal but not in the other, or at least one road that is guarded by troops in one proposal but not in the other.

Input Specification

The first line contains two positive integers n and m, which represent the number of cities and the number of two-way roads, respectively.

The next m lines each containing two positive integers u_i, v_i, describing a two-way road connecting cities u_i and v_i. It is guaranteed that there are no multiple edges or self-loops.

Output Specification

The output should contain one integer, representing the number of ways to build facilities and assign troops to roads, modulo 10^{9}+7.

Sample Input 1

2 1
1 2

Sample Output 1

5

Explanation of Sample 1

Country A has two cities, and a road connects them. All possible scenarios are as follows:

  • Build a facility in city 1, do not guard the road;
  • Build a facility in city 1, guard the road;
  • Build a facility in city 2, do not guard the road;
  • Build a facility in city 2, guard the road;
  • Build facilities in both cities 1 and 2, guard the road.

Sample Input 2

4 4
1 2
2 3
3 1
1 4

Sample Output 2

184

Additional Samples

Additional sample cases can be found here.

Constraints

For all data, 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.

Casen\leqm \leqSpecial Condition
1 - 3810none
4 - 61625
8 - 930005000
10 - 11 5 \times 10^510^6m = n - 1 and road i connects i to i + 1
12 - 14m = n - 1
15 - 16m = n
17 - 20none

Comments

There are no comments at the moment.