【vijos1876】小岛的标号

2014年10月29日1,1330

描述

Xiaodao是一位喜欢参加ACM比赛的孩子.
所谓ACM比赛, 是一种团队比赛.
每一次比赛, 每队需要由恰好三位选手组成.
现在, Xiaodao希望组建一支新的队伍, 在这之前, 他需要知道每一位朋友有多少可能成为自己的好队友.

他计划给每一位朋友做出一个等级标号.
Xiaodao本人的等级标号为0.
如果一位朋友曾经和Xiaodao组队参加过比赛, 那么就标号为1.
如果一位朋友并没有与Xiaodao组队参加过比赛, 但是曾经与一位”与Xiaodao一起参加过比赛的人”组队参加过比赛. 那么就标号为2.
如果一位朋友无法标号为小于等于 k 的整数, 但是曾经与”标号为k的人”一起参加过比赛, 那么便可以标号为k+1.
其余的朋友们, 便无法给出编号, 我们记为”undefined”.

现在, 我们给出了 n 组曾经参赛过的队伍, 每一组中给出了三位选手的名字.
我们希望知道每一位涉及到的选手应该被给予什么样的标号.

格式

输入格式

第一行给出队伍的总数 n (1<=n<=50000).
之后 n 行, 每一行给出了一支队伍中三位选手的名字, 用空格隔开.
每一位选手的名字都是一个非空的英文字符串, 其长度不超过 20. 首字母大写, 其余字母小写.

输出格式

对于输入数据涉及到的所有选手, 需要按照其名字的字典序输出每一位选手的名字与标号.
每一行输出一位选手的信息, 首先是他(她)的名字, 其次是他(她)的标号, 如果标号无法给出, 则输出 “undefined”.

样例1

样例输入1[复制]

样例输出1[复制]

限制

对于40%的数据: 1<=n<=100
对于80%的数据: 1<=n<=10000
对于100%的数据: 1<=n<=50000

时间限制: 每个测试点2秒.

题解。。。map+bfs。。。

map显然不能过100的数据。。。100还是字典树吧