时间限制：1000ms　内存限制：512MB

结果比较方式为全文比较（过滤行末空格及文末换行）。

题目描述

行业协会有 $n$ 家企业，编号为 $1\sim n$。企业之间存在一些合作关系，每条合作关系连接两家不同的企业，任意两家企业之间至多存在一条合作关系。合作关系是相互的：如果企业 $u$ 与企业 $w$ 之间有合作关系，那么企业 $w$ 与企业 $u$ 之间也有。

三家互不相同的企业，若两两之间都有合作关系，就称它们构成一个联盟三角。一家企业可能同时属于多个联盟三角。

每家企业在行业中的影响力用一个正整数 $v_i$ 表示。行业协会需要统计每家企业的两项数据：

1. 包含企业 $i$ 的联盟三角个数 $c_i$；
2. 在所有包含企业 $i$ 的联盟三角中，另外两家企业影响力之和的最大值 $m_i$。若不存在包含企业 $i$ 的联盟三角，则 $m_i = 0$。

请按编号顺序输出每家企业的 $c_i$ 与 $m_i$。

输入格式

从文件 tri.in 中读入数据。

• 第一行两个整数 $n, m$，分别表示企业个数与合作关系条数；
• 第二行 $n$ 个整数 $v_1, v_2, \dots, v_n$，依次表示各企业的影响力；
• 接下来 $m$ 行，每行两个整数 $u_i, w_i$，表示企业 $u_i$ 与企业 $w_i$ 之间存在一条合作关系。

输出格式

输出到文件 tri.out 中。

输出 $n$ 行，第 $i$ 行两个整数 $c_i, m_i$，依次表示包含企业 $i$ 的联盟三角个数，以及所有包含企业 $i$ 的联盟三角中另外两家企业影响力之和的最大值。

样例

样例 1 输入

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

样例 1 输出

1 7
1 5
1 8
0 0
0 0

样例 1 解释

合作关系为 $1$-$2$、$1$-$3$、$2$-$3$、$1$-$4$、$4$-$5$。三家企业两两之间都有合作关系的只有 $1,2,3$ 这一组：$1$-$2$、$1$-$3$、$2$-$3$ 都是合作关系。其余组合如 $1,4,5$ 缺少 $1$-$5$ 这条边，$3,4,5$ 缺少 $3$-$4$、$3$-$5$ 两条边，均不构成联盟三角。企业 $1$ 只在这一组联盟三角中，另外两家是企业 $2,3$，影响力之和为 $5+2=7$，故 $c_1=1$、$m_1=7$。企业 $2$ 的另外两家为企业 $1,3$，影响力之和 $3+2=5$；企业 $3$ 的另外两家为企业 $1,2$，影响力之和 $3+5=8$。企业 $4,5$ 不包含在任何联盟三角中，输出 $0\ 0$。

样例 2 输入

4 2
10 1 1 1
1 2
1 3

样例 2 输出

0 0
0 0
0 0
0 0

样例 2 解释

企业 $1$ 与 $2$、$3$ 各有合作关系，但企业 $2$ 与企业 $3$ 之间没有合作关系，三家企业无法两两相连；企业 $4$ 与任何企业都没有合作关系。整个图中不存在联盟三角，每家企业都不包含在任何联盟三角中，$c_i$ 均为 $0$，按约定 $m_i$ 也输出 $0$。

样例 3 输入

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

样例 3 输出

4 7
3 9
3 8
4 9
1 7
0 0

样例 3 解释

逐组核对三家企业两两之间的合作关系，图中联盟三角共有 $5$ 个：$(1,2,3)$、$(1,2,4)$、$(1,3,4)$、$(1,4,5)$、$(2,3,4)$。

以企业 $1$ 为例，它属于前四个联盟三角，$c_1=4$；四个三角中另外两家影响力之和分别为 $3+4=7$、$3+2=5$、$4+2=6$、$2+1=3$，其中最大的是 $7$，故 $m_1=7$。企业 $4$ 属于 $(1,2,4)$、$(1,3,4)$、$(1,4,5)$、$(2,3,4)$，另外两家影响力之和分别为 $5+3=8$、$5+4=9$、$5+1=6$、$3+4=7$，最大为 $9$，故 $m_4=9$。企业 $6$ 不包含在任何联盟三角中，输出 $0\ 0$。

数据范围

对于所有测试数据，保证：

• $1 \le n \le 10^5$，$0 \le m \le 2\times 10^5$；
• $1 \le v_i \le 10^9$；
• 任意两家企业之间至多存在一条合作关系，不存在某家企业与自身的合作关系。

各测试点的约束如下：

• 特殊性质 A：每家企业的合作关系不超过 $20$ 条。