# PROBLEM LINK:

* Author:* Harendra Chhekur

*Darshan Sen*

**Editorialist:**# DIFFICULTY:

EASY

# PREREQUISITES:

# PROBLEM:

Check whether it is possible to design a network of exactly N computers and exactly M wires such that there exists at most one wire between each and every computer and each computer is directly or indirectly connected with each other.

If possible, find the minimum *data consumption factor* of the **network**. The *data consumption factor* of a **computer** is the number of computers it is directly connected to. The *data consumption factor* of the **network** is the maximum of the *data consumption factors* of all **computers**.

# EXPLANATION:

Let’s stop calling this a computer network and think in terms of a graph. Since this is a greedy approach, let’s discuss a method of adding the M edges (or wires) to a given graph with N vertices (or computers).

The minimum value that M holds for all vertices to be connected is N - 1. Then, the graph would take the form of a Path graph.

The maximum value that is held by M is in the case where we generate a complete graph with all vertices having a self-loop each, i.e.,

M = {N}\choose{2}

(number of edges in a complete graph)+N(self-loops)= N (N + 1) / 2

If the value of M lies beyond the mentioned range, we print -1. If that is not the case, we try to calculate the *data consumption factor* of the graph. We think of a method of adding the edges to the graph optimally, so that the *data consumption factor* is minimized in each case.

We’ll start off with N > 2.

#### Path graph(N - 1 edges)

Here, the *data consumption factor* is 2.

We may add edge #N in between the pair of vertices with degree 1, to either make

a Cycle graph or just add a self-loop to one of the vertices with degree 1.

The *data consumption factor* is still 2.

As we add edge #N + 1, we have a graph that looks like the Path graph with the two end vertices having self-loops. Hence, the *data consumption factor* is still 2.

For edge #N + 2, we join the two vertices with self-loops and get *data consumption factor* to be 3. We keep adding edges in the form of self-loops till we reach edge #2N. We still get *data consumption factor* to be 3.

Now, the scenario has changed. We change our perception of the graph. Since we are not touching the self-loops anymore, let’s denoise the graph we’ve been drawing by removing the obvious self-loops. What have we got now? A simple graph!

Let’s consider that we already have the required graph with M edges connected. The number of edges of the simple graph is:

E = M - N

(removing N self-loops)

sum of degrees=2E

Now, let’s distribute the sum of degrees among all N vertices evenly. The maximum of degrees of all vertices is given by:

maxdeg = \lceil sum of degrees / N \rceil

#### Note:

We need not be concerned about parallel edges coming up in the resultant graph because, in a simple graph, we neither have parallel edges nor self-loops.

Let’s trace ourselves back to the original graph, where we had self-loops.

data consumption factor= maxdeg + 1(adding back the self-loop)

We have solved the problem for values of N>2. Now I’ll list out the solutions one can find out by manually working out the problem for N = 1 and N = 2:

N M

data consumption factor

1 | 0 | 0

1 | 1 | 1

2 | 1 | 1

2 | 2 | 2

2 | 3 | 2

Clearly, the time complexity of the solution is O(1).

Below is a heavily documented code in C++.

# SOLUTIONS:

## Editorialist's Solution

```
#include <iostream>
typedef long long ll;
ll solve (ll N, ll M) {
/*
Spoiler: This is a greedy approach. =D
The minimum value M can hold,
for all the computers to be connected
is N - 1 -- a path graph
The maximum value M can hold,
= Combination(N, 2) // each pair of computers has 1 wire in between
+ N // 1 self loop on each computer
*/
ll res;
if (
M < (N - 1LL)
or
M > ((N * (1LL + N)) >> 1)
) {
res = -1LL;
} else {
if (N == 1LL) {
if (M == 0LL) {
res = 0LL; // Since the computer is connected to itself
} else {
// M == 1LL
res = 1LL;
/*
---1
|__|
*/
}
} else if (N == 2LL) {
if (M == 1LL) {
res = 1LL; // 1 ----- 2
} else if (M == 2LL) {
res = 2LL;
/*
---1 ----- 2
|__|
*/
} else {
// M == 3LL
res = 2LL;
/*
---1 ----- 2---
|__| |__|
*/
}
} else {
if (M <= 1LL + N) {
/*
1st N - 1 wires form a path graph
...
x x
\ /
x x
Nth wire forms a cycle graph
...
x x
\ /
x--x
N+1th wire forms this
...
x x
\ /
--x x--
|_| |__|
*/
res = 2LL;
} else if (M <= (N << 1)) {
/*
cycle graph with
all computers having
1 self-loop each
*/
res = 3LL;
} else {
/*
we remove the
obvious self-loops
and make it a simple graph
*/
ll simple_graph_edges = M - N;
/*
Here we use the simple Handshaking Lemma
: https://en.wikipedia.org/wiki/Handshaking_lemma
*/
ll sum_of_degrees = simple_graph_edges << 1;
/*
Since it is a greedy approach,
we consider that sum_of_degrees will be evenly distributed
among all the computers.
But, if we can't divide sum_of_degrees evenly
among N computers, we have to consider the computer with
the maximum degree. Hence, we find ceil(sum_of_degrees / N).
*/
// ceil of sum_of_degrees / N
ll c = (sum_of_degrees + N - 1LL) / N;
/*
maximum degree(for the simple graph)
+ 1(self-loop)
*/
res = 1LL + c;
}
}
}
return res;
}
int main() {
int T;
std::cin >> T;
while (T--) {
ll N, M;
std::cin >> N >> M;
std::cout << solve(N, M) << std::endl;
}
return 0;
}
```