← 返回题目列表

Codeforces · 1444/C

C. 团队建设

中文机器翻译题面 查看原题

新学年开始了,伯兰德大学有$$$n$$$一年级学生。他们被分为 $$$k$$$ 学术小组,但是,其中一些小组可能是空的。在学生中,有$$$m$$$对熟人,每个熟人对可能都在一个共同的组中,也可能在两个不同的组中。

Alice是第一年的策展人,她想举办一个有趣的游戏,让大家互相认识。为此,她将选择两个不同的学术小组,然后将这些小组的学生分成两个小组。游戏要求每支队伍内不得有熟人对。

Alice 想知道她可以选择多少对组,这样之后就可以玩游戏了。两个选定组的所有学生都必须参加比赛。

请注意,Alice 为游戏组建的团队不需要与学生学习的小组一致。此外,团队的规模可能不同(甚至是空的)。

输入

第一行包含三个整数 $$$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$$$,并且没有(无序)对被多次提及。

输出

打印一个整数 - 选择两个不同组的方式数量,以便可以选择两个团队来玩游戏。

示例

输入 #1

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

输出 #1

2

输入 #2

4 3 3
1 1 2 2
1 2
2 3
3 4

输出 #2

3

输入 #3

4 4 2
1 1 1 2
1 2
2 3
3 1
1 4

输出 #3

0

输入#4

5 5 2
1 2 1 2 1
1 2
2 3
3 4
4 5
5 1

输出#4

0

注意

第一个示例的熟人图如下图所示(每个学生旁边写有他们的组号)。

在该测试中,我们可以选择以下组:

- 选择第一组和第二组。例如,可以由 $$$1$$$ 和 $$$4$$$ 学生组成一支队伍,而 $$$2$$$ 和 $$$3$$$ 学生可以组成另一队。
- 选择第二组和第三组。例如,可由 $$$3$$$ 和 $$$6$$$ 组成一队,而另一队可由 $$$4$$$ 和 $$$5$$$ 学生组成。
- 我们无法选择第一组和第三组,因为无法组建比赛队伍。

在第二个示例中,我们可以选择任何组对。请注意,即使第三组没有学生,我们仍然可以选择它(与其他组)进行游戏。