Italian Data Centers
Contest: SWERC 2022-2023 - Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 2500
Tags: graphs, shortest paths

An Italian data center consists of a set of servers, each colored green, white, or red, and a set of wires connecting them. Each wire connects two distinct servers and two servers are connected by at most one wire. Additionally, the data center is connected, i.e. there is a way to transmit information between any two servers through a sequence of wires.

To judge all of the contestant submissions, SWERC has an Italian data center. Since every year the number of contestants doubles, the data center needs to grow to adapt to the extra load. To address this, SWERC builds a new data center based on the previous year's one by following these steps:

- For each server $$$s$$$ in the old data center, the new data center contains two servers $$$s_1$$$ and $$$s_2$$$ of the same color as $$$s$$$. A wire is placed connecting the two servers $$$s_1$$$ and $$$s_2$$$.
- For each wire connecting servers $$$s$$$ and $$$t$$$ in the old data center: if $$$s$$$ and $$$t$$$ have the same color, then a wire is placed in the new data center connecting $$$s_1$$$ and $$$t_1$$$ and another wire connecting $$$s_2$$$ and $$$t_2$$$; otherwise, a wire is placed in the new data center connecting $$$s_1$$$ and $$$t_2$$$ and another one connecting $$$s_2$$$ and $$$t_1$$$.

One can show that if the old data center is connected than the new data center is also connected.

You are given the Italian data center that SWERC currently has, which contains $$$n$$$ servers (indexed by $$$1, \, 2, \, \dots, \, n$$$) and $$$m$$$ wires connecting them. The organization wants to know how good their data center will be after $$$k$$$ years, so you should determine the diameter of the data center SWERC will have in $$$k$$$ years. The diameter of the data center is the largest distance between any two servers, i.e. the shortest number of wires that have to be used to transmit something between the two servers.

Input format:
The first line contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$2 \leq n \leq 100$$$, $$$n - 1 \leq m \leq n (n - 1) / 2$$$, $$$0 \leq k \leq 100$$$) — the number of servers, the number of wires, and the number of years to consider.

The second line contains $$$n$$$ integers $$$c_1, \, c_2, \, \dots, \, c_n$$$ ($$$1 \leq c_i \leq 3$$$) — $$$c_i$$$ is the color of server $$$i$$$ (where $$$1$$$ stands for green, $$$2$$$ for white and $$$3$$$ for red).

Each of the next $$$m$$$ lines contains two integers $$$s_i$$$ and $$$t_i$$$ ($$$1 \leq s_i, t_i \leq n$$$) — the two servers the $$$i$$$-th wire connects.

It is guaranteed that the data center is connected, the endpoints of each wire are distinct, and that there are no repeated wires.

Output format:
Print the diameter of SWERC's data center after $$$k$$$ years.

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

Note:
In the first sample, the Italian data center is the following:

The distance between any pair of servers is $$$1$$$ so the diameter is $$$1$$$.

In the second sample, the initial Italian data center is the one from the first sample.

After one year we obtain the following (where the numbers indicate which copy the server refers to):

Consider the highlighted servers. The distance between them is $$$2$$$ and there is no pair of servers with greater distance, so the diameter is $$$2$$$.

In the third sample, the data center after one year is the following:

After one more year:

Consider the highlighted servers. The distance between them is $$$3$$$ and there is no pair of servers with greater distance, so the diameter is $$$3$$$.

Example input:
3 3 0
1 2 3
1 2
2 3
3 1

Example output:
1

Example input:
3 3 1
1 2 3
1 2
2 3
3 1

Example output:
2

Editorial:
This problem is ultimately about graphs, so let's start by translating the statement into a more formal language using graphs. Let $$$G = (V, E)$$$ be a graph with $$$|V| = n$$$ vertices and $$$|E| = m$$$ edges, where each vertex is colored in one of three colors. The problem statement describes an operation we shall call doubling, since in a way it "doubles" the graph. The double of $$$G$$$, denoted by $$$d(G)$$$, is a graph with $$$2n$$$ vertices and $$$2m + n$$$ edges defined as such:
1. For each $$$v \in V$$$, the double graph $$$d(G)$$$ contains two copies of $$$v$$$ of the same color, $$$v_1$$$ and $$$v_2$$$. There is also an edge connecting $$$v_1$$$ and $$$v_2$$$ in $$$d(G)$$$.
2. For each $$$\{v, u\} \in E$$$: if $$$v$$$ and $$$u$$$ have the same color, then $$$d(G)$$$ contains an edge between $$$v_1$$$ and $$$u_1$$$, and an edge between $$$v_2$$$ and $$$u_2$$$; otherwise, $$$d(G)$$$ contains an edge between $$$v_1$$$ and $$$u_2$$$, and an edge between $$$v_2$$$ and $$$u_1$$$.
Now consider applying this doubling operation $$$k$$$ times to $$$G$$$. Our goal is to find the diameter of the resulting graph, i.e. the largest distance (shortest path) between any two vertices in the graph $$$\underbrace{d(d(\cdots d(}_{k \text{ times}}G)\cdots))$$$. Let $$$G_i$$$ be the graph after $$$i$$$ doubling operations, so $$$G_i = \underbrace{d(d(\cdots d(}_{i \text{ times}}G)\cdots))$$$.
Dissecting the problem
At first glance the problem sounds really hard, one has to compute the diameter of an exponentially sized graph ($$$2^kn$$$ vertices), so we have to study the structure of the problem to gain some intuition.
Observation 1. Each vertex of $$$G$$$ is copied $$$2^k$$$ times in $$$G_k$$$, so we can describe each vertex in $$$G_k$$$ by a vertex in $$$G$$$ and a length-$$$k$$$ bitstring. For example, $$$(v, {\tt 011 })$$$ would represent $$$((v_1)_2)_2$$$, so the second copy of the second copy of the first copy of $$$v$$$.
Before we continue with our study of the doubling process let's make one definition.
Definition 1. The hypercube graph of dimension $$$n$$$ is a graph with $$$2^n$$$ vertices given by all length-$$$n$$$ bitstrings such that there is an edge between two vertices if their associated bitstrings differ in exactly one element (i.e. if the Hamming distance between them is 1).
Observation 2. The edges in $$$G_k$$$ between copies of a vertex $$$v$$$ from $$$G$$$ form an hypercube graph of dimension $$$k$$$, in other words, each subgraph of $$$G_k$$$ induced by all of the copies of a single vertex forms an hypercube graph of dimension $$$k$$$.
This is easy to see inductively, but for completeness here is a proof: consider the subgraph in $$$G_{i-1}$$$ induced by all the copies of $$$v \in V$$$ and assume this forms an hypercube graph of dimension $$$i-1$$$. When forming $$$G_i$$$ notice that since all of the vertices have the same color, step 2 of the doubling operation creates two copies of subgraph induced by the copies of $$$v$$$ in $$$G_{i-1}$$$. The first copy has all the vertices whose bitstring starts with a 0 in the $$$G_i$$$ representation, and the second copy has are all the vertices whose bitstring starts with a 1. All the vertices in the first copy differ in the first bit from the ones on the second copy, so to form an hypercube graph of dimension $$$i$$$ we need to add an edge between vertices with the same $$$i-1$$$ last bits, which is exactly what step 1 of the doubling operation does.
Now that we understand the structure of copies of a single vertex, let's describe the edges between copies of different vertices of $$$G$$$. To make our notation easier to read, we refer to a vertex from $$$G_i$$$ as $$$(v, b)$$$, where $$$v \in V$$$ and $$$b$$$ is a length-$$$i$$$ bitstring.
Observation 3. Assume that $$$\{u, v\} \in E$$$. Consider a vertex $$$(u, b)$$$ from $$$G_k$$$, where $$$b$$$ is a length-$$$k$$$ bitstring. $$$(u, b)$$$ is connected to exactly one copy of $$$v$$$ which is $$$(v, b)$$$ if $$$v$$$ and $$$u$$$ have the same color, or $$$(v, \overline{b})$$$ if they have different colors, where $$$\overline{b}$$$ is the bitwise-negation of $$$b$$$.
We can see why this is true by noting that if $$$v$$$ and $$$u$$$ have the same color, then all the copies of $$$u$$$ will be connected to the corresponding copy of $$$v$$$. If $$$v$$$ and $$$u$$$ have different colors, then we can see the observation by thinking inductively. Let $$$b^{(i)}$$$ be the length-$$$i$$$ suffix of $$$i$$$. When creating $$$G_i$$$ from $$$G_{i - 1}$$$ we go from $$$(u, b^{(i-1)})$$$ to $$$(u, b^{(i)})$$$ by adding $$$b_i$$$ to the beginning of $$$b^{(i-1)}$$$. Since $$$u$$$ and $$$v$$$ have different colors, we connect $$$(u, b^{(i)})$$$ to $$$(v, \overline{b_i}\overline{b^{(i-1)}}) = (v, \overline{b^{(i)}})$$$.
Observation 4. Let $$$(u_1, b_u^1), (u_2, b_u^2), \ldots, (u_\ell, b_u^\ell)$$$ be a path in $$$G_k$$$. Then there is a valid path of the same length $$$(v_1, b_v^1), (v_2, b_v^2), \ldots, (v_\ell, b_v^\ell)$$$ and an index $$$i$$$ such that $$$v_1 \neq v_2$$$ and $$$v_2 \neq v_3$$$, ..., $$$v_{i-1} \neq v_i$$$ and $$$v_i = v_{i+1} = \ldots = v_\ell$$$, so we first take all steps that move between vertices of $$$G$$$ and then we take only steps in copies of $$$v_i$$$.
We obtain this by "rearranging" the steps in the first path. Given the symmetry of the graph, if we take one step between two copies of the same vertex too early, we can take that step at the end instead.
Computing the diameter
Let's start by describing the distance between two vertices $$$(u, b_u)$$$ and $$$(v, b_v)$$$ from $$$G_k$$$, where $$$b_u$$$ and $$$b_v$$$ are length-$$$k$$$ bitstrings and $$$u, v \in V$$$ (not necessarily connected or distinct). But first, a quick definition:
Definition 2. Let $$$P$$$ be a path in $$$G$$$ between $$$u$$$ and $$$v$$$. We call $$$P$$$ an even path if the number of multicolored edges it uses is even, i.e. the number of times it walks to a vertex of a different color from the previous one is even. We analogously define odd paths.
Observation 5. The length of the shortest path between $$$(u, b_u)$$$ and $$$(v, b_v)$$$ is given by the shortest of the following:
• The length of the shortest even path between $$$u$$$ and $$$v$$$ plus $$$\Delta(b_u, b_v)$$$, where $$$\Delta(x, y)$$$ represents the Hamming distance between $$$x$$$ and $$$y$$$, i.e. the number of positions at which the corresponding bits differ.
• The length of the shortest odd path between $$$u$$$ and $$$v$$$ plus $$$\Delta(b_u, \overline{b_v})$$$.
Proof. Consider a path in $$$G_k$$$ of length $$$\ell$$$ from $$$(u, b_u)$$$ to $$$(v, b_v)$$$, say $$$(u_1, b_u^1), (u_2, b_u^2), \ldots, (u_\ell, b_u^\ell)$$$, where each pair of consecutive vertices is connected and $$$(u_1, b_u^1) = (u, b_u)$$$ and $$$(u_\ell, b_u^\ell) = (u_v, b_v)$$$. Without loss of generality, we can assume that there is an $$$i$$$ such that $$$u_1 \neq u_2$$$ and $$$u_2 \neq u_3$$$, ..., $$$u_{i-1} \neq u_i$$$ and $$$u_i = u_{i+1} = \ldots = v$$$, by Observation 4.
We can "project" this path down to $$$G$$$, i.e. drop all bitstring labels to obtain $$$u_1, u_2, \ldots, u_\ell$$$. Note that this projected path is a path between $$$u$$$ and $$$v$$$. If the projected path is an even path, then using Observation 3 we conclude that the $$$i$$$th vertex is $$$(v, b_u)$$$, otherwise it is $$$(v, \overline{b_u})$$$. In the even case, the distance between $$$(v, b_u)$$$ and $$$(v, b_v)$$$ is given by $$$\Delta(b_u, b_v)$$$, and in the odd case the distance between $$$(v, \overline{b_u})$$$ and $$$(v, b_v)$$$ is $$$\Delta(\overline{b_u}, b_v)$$$. This concludes the proof. $$$\square$$$
Now, we can use this observation to describe the solution to the problem. First, because of the symmetries of the doubling operation, note that given a path $$$(u_1, b_u^1), (u_2, b_u^2), \ldots, (u_\ell, b_u^\ell)$$$, there is another valid path $$$(u_1, {\tt 00\ldots0}), (u_2, (b_u^2)'), \ldots, (u_\ell, (b_u^\ell)')$$$, which is obtained by inverting all the $$${\tt 1}$$$ bits of $$$b_1$$$. This means that to find the diameter of $$$G_k$$$ we only need to look at paths that start on vertices of the form $$$(v, {\tt 00\ldots0})$$$.
Given $$$u, v$$$ from $$$G$$$, let's try to determine the $$$b$$$ that maximizes the distance between $$$(u, {\tt 00\ldots0})$$$ and $$$(v, b)$$$. From Observation 4 and 5, we know that we either first take an even path from $$$(u, {\tt 00\ldots0})$$$ to $$$(v, {\tt 00\ldots0})$$$, or an odd path from $$$(u, {\tt 00\ldots0})$$$ to $$$(v, {\tt 11\ldots1})$$$. Let $$$|b| = x$$$, i.e. the number of 1s in $$$b$$$ is $$$x$$$. Then, the distance from $$$(v, {\tt 00\ldots0})$$$ to $$$(v, b)$$$ is given by $$$x$$$ and the distance from $$$(v, {\tt 11\ldots1})$$$ to $$$(v, b)$$$ is given by $$$k - x$$$. Let's denote $$$\delta_e(u, v)$$$ be the shortest even path between $$$u$$$ and $$$v$$$, and define $$$\delta_o(u, v)$$$ analogously. Then the maximum distance between $$$(u, {\tt 00\ldots0})$$$ and $$$(v, b)$$$ for any $$$b$$$, is given by $$$\max_{0\leq x \leq k} \{\delta_e(u, v) + x, \delta_o(u, v) + k - x\}$$$.
So here is a possible algorithm:
Algorithm. For every pair of vertices $$$u, v$$$ from $$$G$$$, compute the length of the shortest even path ($$$\delta_e(u, v)$$$), and the shortest odd path between them ($$$\delta_e(u, v)$$$). We can do this by running a Breadth-First Search starting at $$$u$$$ that also keeps track of the parity of the number of times we've traversed multicolored edges. Then we compute $$$\max_{0\leq x \leq k} \{\delta_e(u, v) + x, \delta_o(u, v) + k - x\}$$$ and output the maximum of this over all pairs.
Note that this algorithm runs in time $$$O(nm + n^2k)$$$, since we need one BFS per vertex (which takes $$$O(nm)$$$ time) and then for each pair of vertices we need to compute $$$\max_{0\leq x \leq k} \{\delta_e(u, v) + x, \delta_o(u, v) + k - x\}$$$ (which takes $$$O(n^2k)$$$ time). This can be improved to $$$O(nm + n^2)$$$, but that isn't necessary for this problem since $$$n, k \leq 100$$$.