# PROBLEM LINKS:

### DIFFICULTY

HARD

### EXPLANATION

Let’s focus on finding the number of vertices and edges of **G _{2}** first. According to the problem statement, each vertex of

**G**corresponds to an edge of

_{1}**G**, and each edge of

_{0}**corresponds to a pair of edges of**

_{}**sharing a common vertex. That means that each vertex of**

_{}**G**corresponds to a pair of edges of

_{2}**G**sharing a common vertex as well, and a bit of thinking on paper leads to a conclusion that each edge of

_{0}**G**corresponds to two pairs of edges of

_{2}**G**(each pair sharing a common vertex in

_{0}**G**) sharing a common edge.

_{0}Both numbers can be calculated in a fairly easy way now. For the number of vertices of

**G**, let’s consider each vertex of

_{2}**G**as the shared vertex between two edges. Suppose this vertex has degree (the number of outgoing edges) equal to

_{0}**D**. Then it’s easy to see that there are D *(D-1)/2 pairs of edges sharing this particular vertex. For the number of edges of

**G**, let’s consider each edge of

_{2}**G**as the shared edge between two pairs of edges. Suppose the total degree of this edge’s ends is equal to

_{0}**D**. Then, again, there are

**D * (D-1)/2**pairs of pairs of edges sharing this particular edge. As the degrees of all vertices can be easily calculated in O(

**M**) time, the number of vertices and edges in

**G**can be calculated in the same time.

_{2}The last thing to notice is that graph

**G**is not really big. It has at most 1000 vertices, and in the worst case it has 1000 * 999/2 = 499500 edges, so it’s enough to write down

_{1}**G**explicitly and then use the aforementioned algorithm to find the number of vertices and edges in

_{1}**G**, as required.

_{3}### SETTER’S SOLUTION

Can be found here.

### TESTER’S SOLUTION

Can be found here.