CF1444C.Team-Building

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).

新学年已经开始，Berland 大学共有 $n$ 名一年级学生。他们被划分为 $k$ 个学术小组，但其中某些小组可能为空。在这些学生中，存在 $m$ 对相互认识的同学，每一对相识关系中的两人可能同属一个小组，也可能分属两个不同的小组。

Alice 是一年级学生的辅导员，她打算组织一场趣味游戏，以帮助所有学生彼此熟识。为此，她将选出两个不同的学术小组，并将这两个小组中的所有学生划分为两支队伍。游戏要求：每支队伍内部均不能存在相识关系（即任意一支队伍中不能包含某对相识的同学）。

Alice 想知道：有多少种选择两个不同小组的方式，使得在此之后能够成功组织这场游戏？注意：所选两个小组中的所有学生都必须参加该游戏。

请注意，Alice 为游戏所划分的两支队伍无需与学生原本所在的学术小组一致；此外，两支队伍的规模可以不同（甚至允许某支队伍为空）。

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.

第一行包含三个整数 $n$、$m$ 和 $k$（$1 \le n \le 500\,000$；$0 \le m \le 500\,000$；$2 \le k \le 500\,000$），分别表示学生人数、熟人对数以及组数。

第二行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$（$1 \le c_i \le k$），其中 $c_i$ 表示第 $i$ 个学生的所属组号。

接下来是 $m$ 行。第 $i$ 行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le n$），表示学生 $a_i$ 和 $b_i$ 彼此熟识。保证 $a_i \neq b_i$，且任意无序对至多出现一次。

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.

输出一个整数——选择两个不同小组的方式数，使得可以从中选出两支队伍进行比赛。

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.

第一个示例的熟人关系图如下图所示（每位学生旁边标有其所在组的编号）。

在该测试用例中，我们可以选择以下组对：

• 选择第一组和第二组。例如，一支队伍可由学生 $1$ 和 $4$ 组成，另一支队伍可由学生 $2$ 和 $3$ 组成。
• 选择第二组和第三组。例如，一支队伍可由学生 $3$ 和 $6$ 组成，另一支队伍可由学生 $4$ 和 $5$ 组成。
• 我们不能选择第一组和第三组，因为无法为该游戏组成有效的队伍。

在第二个示例中，我们可以任选两组组成组对。请注意，尽管第三组没有学生，我们仍可将其（与另一组一起）选入该游戏。