Team-Building
Contest: Codeforces Round 680 (Div. 1, based on Moscow Team Olympiad)
Difficulty rating: 2500
Tags: data structures, dfs and similar, dsu, graphs

The new academic year has started, and Berland's university has $$$n$$$ first-year students. They are divided into $$$k$$$ academic groups, however, some of the groups might be empty. Among the students, there are $$$m$$$ pairs of acquaintances, and each acquaintance pair might be both in a common group or be in two different groups.

Alice is the curator of the first years, she wants to host an entertaining game to make everyone know each other. To do that, she will select two different academic groups and then divide the students of those groups into two teams. The game requires that there are no acquaintance pairs inside each of the teams.

Alice wonders how many pairs of groups she can select, such that it'll be possible to play a game after that. All students of the two selected groups must take part in the game.

Please note, that the teams Alice will form for the game don't need to coincide with groups the students learn in. Moreover, teams may have different sizes (or even be empty).

Input format:
The first line contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$1 \le n \le 500\,000$$$; $$$0 \le m \le 500\,000$$$; $$$2 \le k \le 500\,000$$$) — the number of students, the number of pairs of acquaintances and the number of groups respectively.

The second line contains $$$n$$$ integers $$$c_1, c_2, \dots, c_n$$$ ($$$1 \le c_i \le k$$$), where $$$c_i$$$ equals to the group number of the $$$i$$$-th student.

Next $$$m$$$ lines follow. The $$$i$$$-th of them contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$), denoting that students $$$a_i$$$ and $$$b_i$$$ are acquaintances. It's guaranteed, that $$$a_i \neq b_i$$$, and that no (unordered) pair is mentioned more than once.

Output format:
Print a single integer — the number of ways to choose two different groups such that it's possible to select two teams to play the game.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
The acquaintances graph for the first example is shown in the picture below (next to each student there is their group number written).

In that test we can select the following groups:

- Select the first and the second groups. For instance, one team can be formed from students $$$1$$$ and $$$4$$$, while other team can be formed from students $$$2$$$ and $$$3$$$.
- Select the second and the third group. For instance, one team can be formed $$$3$$$ and $$$6$$$, while other team can be formed from students $$$4$$$ and $$$5$$$.
- We can't select the first and the third group, because there is no way to form the teams for the game.

In the second example, we can select any group pair. Please note, that even though the third group has no students, we still can select it (with some other group) for the game.

Example input:
6 8 3
1 1 2 2 3 3
1 3
1 5
1 6
2 5
2 6
3 4
3 5
5 6

Example output:
2

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

Example output:
3

Editorial:
You're given an undirected graph without loops and multiple edges, each vertex has some color from $$$1$$$ to $$$k$$$. Count the number of pairs of colors such that graph induced by vertices of these two colors will be bipartite.
Let's check for each color whether the graph induced by it is bipartite (for example, using depth-first search). This can be done in $$$O(n + m)$$$. We will not use non-bipartite colors further since they can't be in any pairs.
Now let's construct a slow solution that we will make faster later.
Consider some color $$$x$$$. There're edges from vertices of this color to vertices of colors $$$y_1, y_2, \ldots, y_k$$$. Let's check whether the graphs induced by pairs $$$(x, y_1), (x, y_2), \ldots, (x, y_k)$$$ are bipartite (also using depth-first search), thereby finding out which colors cannot be in pair with $$$x$$$. The others can. After doing this for each color $$$x$$$, we can find the asnwer.
How fast does this work? Notice that any edge between different colors we will use in DFS only two times. The problem are edges between vertices of the same color, we can use them up to $$$k$$$ times, and there can be a lot of them.
Let's solve this problem and construct a faster solution.
A graph is bipartite if and only if it doesn't contains odd cycles. Consider some connected bipartite component induced by color $$$x$$$. If a cycle goes through this component, it doesn't matter how exactly it does it. If the path of the cycle in this component ends in the same side where it has started, then it has even length, and odd otherwise. This fact lets us compress this component to two vertices (one for each side) connected by one edge. For each color this way we compress all components formed by it.
Now we have the compressed graph, where all connected components are either one vertex or two vertices connected by one edge. Let's do the same process we did in slow solution and check every connected pair of colors whether the graph induced by it is bipartite.
To check the pair $$$(x, y)$$$, for each edge between vertices of colors $$$x$$$ and $$$y$$$ in the original graph add a new edge to the compressed graph between corresponding vertices. After that use DFS to check if graph is bipartite, rollback the changes and do the same for all other pairs.
How long does this work for one pair $$$(x, y)$$$?
Let's start DFS only from components that were connected by added edges, since the others do not affect whether the graph is bipartite or not, but there can be a lot of them. This way DFS will use only added edges and some edges between vertices of the same color $$$x$$$ or $$$y$$$. However, there will be at most two times more of the latter than the added, because each added edge connects at most two new components, and each new component has at most one edge. So, we check one pair in the time proportional to amount of edges between its colors, and it sums up to $$$O(m)$$$ for all pairs.
So, the whole solution works in $$$O(n + m)$$$ or $$$O(m \log n)$$$, depending on the implementation.