# Editorial for NINENINE - PELT2019

Problem setter: panik

Problem Code: NINENINE

Difficulty: Medium-Hard

Prerequisites: Finding Bridges in a graph in linear time, Combinatorics, Inclusion Exlusion Principle…

Explanation:
First of all, you need to calculate the bridges in the graph in linear time, since the graph must remain connected at every step i.e during deletion and insertion.

1.) G4G

After you have obtained the set of Bridges, you now need to precalculate some things which would later prove to be helpful.

1.)save all the edges of the Graph in an unordered Set. This can be done in nearly Linear time.

2.) For each vertex find the count of vertices connected to it having a particular degree for each kind of available degree. Store this information in a vector of maps which contains this information for each node. This can be done in O(M).

3.) Store the count of edges between vertex of degree x and vertex of degree y for all possible edges available in the graph. Store this information in a map which stores the count of edges between a particular degree x to a particular degree y. This can be done in O(M)

4.) Make a frequency array and find the count of vertices of each particular degree.

Now comes the time to finally start calculating all the possible graphs.

Start Traversing all the edges in Graph.

If the edge is available in the set of bridge edges, then skip this edge

If not,

Temporarily reduce the degree of both the vertices of the edge and reflect this change only in the frequency array. So the count of original degree frequencies reduces by 1 and the new degree frequency increase by 1.
This change would be reverted later.

If the degree of both the vertices is same p= (freq[degree]X(freq[degree]-1))/2 -1

Else p= freq[degree1]*freq[degree2] - 1

Now we need to remove some cases from p to remove the cases where multiple edges occurred in some possible graphs i.e edge already exist in the graph. We also need to add some cases in p because of change in the degree of some vertex due to which count of edges between two particular degrees would change, so some extra cases would be subtracted from p when subtracting those edges which already exist in the graph. This can be done by some observation in the graph

Refer to the solution for better clarity.