问题2262--master

2262: master

时间限制: 1 Sec  内存限制: 256 MB
提交: 81  解决: 21
[状态] [讨论版] [提交] [命题人:]
题目描述

N个人,编号为1N,他们相互之间拜师学艺。

某个时刻,如果甲向乙拜师,一般情况下乙就将甲收为徒弟。这时乙会将甲视为大徒弟,而所有甲的徒弟(如果有的话)便成为乙的小徒弟。

但是,每个人都不想收太多的大徒弟。如果乙当前大徒弟数量超过他的期望值,他便会拒绝甲,而让甲拜自己的某一位大徒弟为师。甲总是想选好的师傅,而如果一个人的所有徒弟数量很多,往往说明他水平比较高,所以甲会选乙的徒弟中,拥有最多徒弟的人。如果有不止一个人徒弟最多,甲会选择最早向乙拜师的那位。于是接下来,就是新的一次拜师过程,甲向乙的某位徒弟拜师。甲直到拜师成功才会停止。

每个人每一时刻最多只会有一个师傅。有师傅的人若再向其他人拜师,就会先断绝与当前师傅的师徒关系。若甲不认乙为师,乙也就不认甲为大徒弟,同时甲和他的徒弟们也因此与甲的师傅脱离关系(当然包括师傅的师傅,师傅的师傅的师傅……)。

两个人之间的师徒关系可能是变化的。所以若甲向乙多次拜师,则甲向乙拜师的时间将以最后一次拜师的时间算。

一开始,每个人都没有师傅,也没有徒弟。我们事先告诉你每个人愿意收的最多大徒弟数量,达到了这个数量,他就不再收大徒弟,除非又有某个大徒弟与他断绝了关系。接下来每一时刻,就有人相互拜师,而所有拜师都会按照上面的规则进行。此外,一个人也不会向自己当前的任何一位徒弟拜师。
请你统计,所有拜师过程结束后,每个人有多少大徒弟,小徒弟。

输入

第一行给出两个整数NM5<=N<=100000<=M<=10000),其中N表示总人数,M表示有多少组拜师的人。

第二行,包含N个正整数,依次表示每个人愿意收的最多大徒弟的数量。

接下来M行,每行两个整数AB,按时间顺序依次表示一对拜师的人。总是AB拜师。

输出

输出包括N行,每行有两个整数,之间用一个空格隔开。第i行的两个数分别表示,在所有拜师结束后,编号为i的人拥有的大徒弟数量和小徒弟数量。

样例输入 Copy
6 7
2 2 2 2 2 2
2 1
3 1
4 1
5 1
6 1
6 3
3 2
样例输出 Copy
1 4
2 2
1 0
1 1
0 0
0 0
来源/分类