Blue and Red of Our Faculty!
Contest: 2020 ICPC, COMPFEST 12, Indonesia Multi-Provincial Contest (Unrated, Online Mirror, ICPC Rules, Teams Preferred)
Difficulty rating: 2600
Tags: divide and conquer, dp

It's our faculty's 34th anniversary! To celebrate this great event, the Faculty of Computer Science, University of Indonesia (Fasilkom), held CPC - Coloring Pavements Competition. The gist of CPC is two players color the predetermined routes of Fasilkom in Blue and Red. There are $$$N$$$ Checkpoints and $$$M$$$ undirected predetermined routes. Routes $$$i$$$ connects checkpoint $$$U_i$$$ and $$$V_i$$$, for $$$(1 \le i \le M)$$$. It is guaranteed that any pair of checkpoints are connected by using one or more routes.

The rules of CPC is as follows:

- Two players play in each round. One player plays as blue, the other plays as red. For simplicity, let's call these players $$$Blue$$$ and $$$Red$$$.
- $$$Blue$$$ will color every route in he walks on blue, $$$Red$$$ will color the route he walks on red. Both players start at checkpoint number $$$1$$$. Initially, all routes are gray.
- Each phase, from their current checkpoint, $$$Blue$$$ and $$$Red$$$ select a different gray route and moves to the checkpoint on the other end of the route simultaneously.
- The game ends when $$$Blue$$$ or $$$Red$$$ can no longer move. That is, there is no two distinct gray routes they can choose to continue moving.

Chaneka is interested in participating. However, she does not want to waste much energy. So, She is only interested in the number of final configurations of the routes after each round. Turns out, counting this is also exhausting, so Chaneka asks you to figure this out!

Two final configurations are considered different if there is a route $$$U$$$ in a different color in the two configurations.

Input format:
The first line contains two integers $$$N$$$ and $$$M$$$. $$$N$$$ $$$(2 \le N \le 2 \cdot 10^3)$$$ denotes the number of checkpoints, $$$M$$$ $$$(1 \le M \le 2 \cdot N)$$$ denotes the number of routes. It is guaranteed that every checkpoint except checkpoint $$$1$$$ has exactly two routes connecting it.

The next $$$M$$$ lines each contains two integers $$$U_i$$$ and $$$V_i$$$ $$$(1 \le U_i, V_i \le N, U_i \ne V_i)$$$, which denotes the checkpoint that route $$$i$$$ connects.

It is guaranteed that for every pair of checkpoints, there exists a path connecting them directly or indirectly using the routes.

Output format:
Output a single integer which denotes the number of final configurations after each round of CPC modulo $$$10^9 + 7$$$

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
Every possible final configuration for the example is listed below:

The blue-colored numbers give the series of moves $$$Blue$$$ took, and the red-colored numbers give the series of moves $$$Red$$$ took.

Example input:
5 6
1 2
2 3
3 4
4 1
1 5
5 1

Example output:
8

Editorial:
First, we must notice that the graph is a clover graph. The graph has cycles with vertex $$$1$$$ in common. We can transform the graph into an array $$$A$$$, where $$$A_i$$$ is the number of edges in cycle $$$i$$$.
On the final configuration, each cycle has three possible endings:
• The whole cycle is colored red or blue
• The whole cycle is gray
• exactly one cycle is colored in two different colors (can be red and blue, red and gray, blue and gray). This is the last cycle they visit.
The third point suggests a dynamic programming approach: for each cycle in $$$A$$$, set this cycle as the last cycle, and count how many configurations. So for the other cycles, we can calculate $$$DP[i][diff][takeAll]$$$, the number of configurations using the first $$$i$$$ cycles, where $$$diff$$$ is the absolute difference between the number edges blue and red took, and $$$takeAll$$$ is a boolean that indicates all cycles 1...i must be taken by either $$$red$$$ or $$$blue$$$. The transitions are quite straightforward, and its easier to see the code if you are confused. Calculating this DP is done in $$$O(N^2)$$$
Why flag $$$takeAll$$$? because for a fixed last cycle, there are two possible final positions for $$$red$$$ and $$$blue$$$, assuming $$$C$$$ is the size of the fixed cycle:
1. If one player ends in vertex $$$1$$$: $$$2 \cdot DP[N][C-1][1]$$$. All other cycles must be colored, else both players can still move.
2. If both players ends inside the cycle: $$$2 \cdot \sum\limits_{i=0}^{C-2}DP[N][i][0]$$$
There is an additional case where both players finish at vertex $$$1$$$. TO find this, we recalculate DP using the whole array. The number of configurations is $$$DP[N][0][1]$$$.
Calculating this for all elements of $$$A$$$ will give an $$$O(N^3)$$$ solution. However, since $$$\sum A = N$$$, there are atmost $$$\sqrt{N}$$$ different values in $$$A$$$. So, we can calculate DP for only these $$$\sqrt{N}$$$ values. This gives a $$$O(N^2 \sqrt{N})$$$ solution which if sufficient to get accepted.
Bonus $$$O(N^2)$$$ solution: The solution can be optimized further by partitioning $$$A$$$ into two parts:
1. first part consists of all distinct values in the area (each appears once). The size of this part is at most $$$\sqrt{N}$$$.
2. the second part is all other elements
We notice that when fixing cycles, the second part does not change so we can calculate DP on this part exactly once in $$$O(N^2)$$$. We can then only recalculate DP in the first part. Since there are $$$\sqrt{N}$$$ elements, calculating DP on this is $$$O(N \sqrt{N})$$$. Since we calculate DP $$$\sqrt{N}$$$ times, the total complexity is $$$O(N^2)$$$. Then, merges with the first DP.