There is a network of $n$ servers labeled from $0$ to $n - 1$. You are given a $2$D integer array edges, where each edges[i] = [u_i, v_i] represents a bidirectional communication link between server $u_i$ and server $v_i$. It takes $1$ second for a message to travel across any single edge. The network is connected, meaning every server can communicate with every other server directly or indirectly.

Server $0$ is designated as the master server, and all other servers from $1$ to $n - 1$ are data servers. Each message sent to the master server travels along the shortest path. Upon receiving a message, the master server instantly processes it and sends an immediate reply back to the originating server along the same shortest path in reverse.

You are also given an integer array patience of length $n$. At the start of second $0$, every data server sends a single message to server $0$. Each data server $i$ will continue monitoring for a reply. If patience[i] seconds have elapsed since its most recent transmission and it has not yet received any reply, server $i$ will resend the message. This resending repeats every patience[i] seconds until server $i$ receives its first reply. Once a data server receives any reply, it immediately stops sending messages.

Return the earliest second at which the network becomes idle, meaning there are no messages in transit between any servers.

Constraints:

• n == patience.length

• $2 \leq n \leq 10^5$

• patience[0] $= 0$

• $1 \leq$ patience[i] $\leq 10^5$ for $1 \leq i < n$

• $1 \leq$ edges.length $\leq \min(10^5, \frac{n \cdot (n - 1)}{2})$

• edges[i].length $= 2$

• $0 \leq u_i, v_i < n$

• $u_i \neq v_i$

• There are no duplicate edges.

• Each server can directly or indirectly reach another server.

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.