作为文化课大师，skip 蚤的大脑中组织着一份复杂的知识网络。

skip 蚤的知识网络中有 $n$ 个知识点，不妨将它们从 $1$ 至 $n$ 编号。skip 蚤在刷题历程中遇见过 $m$ 道令其印象深刻的习题，其中第 $i$ 道题在知识点 $u_i$ 和 $v_i$ 之间建立了联系。同时，每个知识点恰有一个标签，为了知识整理的便捷，标签的数量不会很多，只有 $k$ 个，不妨从 $1$ 至 $k$ 将它们编号。

知识网络帮助 skip 蚤从一个知识点快速发散思考到其他的知识点。定义思考序列为一个由知识点构成的序列 $a_1,a_2,\cdots ,a_r$，满足对于所有 $1\le i\le r-1$，要么知识点 $a_i$ 与 $a_{i+1}$ 之间建立了联系，要么知识点 $a_i$ 与 $a_{i+1}$ 拥有相同的标签。

为了考察发散思考的便捷程度，skip 蚤对两个不同的知识点 $1\le p<q\le n$ 定义知识网络上 $p,q$ 的思考便捷值 $f(p,q)$ 为满足序列起始为 $p$、末尾为 $q$ 的思考序列的最短长度，如果不存在这样的序列，则 $f(p,q)=2k+1$。

skip 蚤想知道：对于 $1\le x\le 2k+1$，有多少个二元组 $(p,q)(1\le p<q\le n)$ 满足 $f(p,q)=x$？

输入格式

第一行三个整数 $n,m,k$，分别表示知识网络中的知识点数、联系数和标签数。

第二行 $n$ 个整数 $p_1,p_2,\cdots ,p_n$，其中 $p_i$ 表示编号为 $i$ 的知识点拥有的标签编号。

接下来 $m$ 行每行两个整数 $u_i,v_i$，表示在知识网络中知识点 $u_i$ 与知识点 $v_i$ 之间建立了联系。

输出格式

输出一行 $2k+1$ 个数，第 $i$ 个数表示有多少个二元组 $(p,q)(1\le p<q\le n)$ 满足 $f(p,q)=i$。

样例一

input

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

output

0 5 3 2 0 0 5

explanation

$f(2,3)=f(3,4)=f(4,5)=f(5,6)=f(4,6)=2$

$f(2,4)=f(3,5)=f(3,6)=3$

$f(2,5)=f(2,6)=4$

$f(1,2)=f(1,3)=f(1,4)=f(1,5)=f(1,6)=7$

样例二

见附加文件中 ex_knowledge2.in 与 ex_knowledge2.out，该组样例满足 $n,m\le 3000$。

样例三

见附加文件中 ex_knowledge3.in 与 ex_knowledge3.out，该组样例无特殊性质。

数据范围

对于 $100\mathrm{\%}$ 的数据，$1\le n\le 5\times {10}^4,0\le m\le 5\times {10}^4,1\le k\le 150,1\le p_i\le k,1\le u_i,v_i\le n,u_i\ne v_i$。

时间限制：$4\mathtt{\text{s}}$

空间限制：$256\mathtt{\text{MB}}$

下载

样例数据下载