题目解读

题目要求在一系列补丁版本的迭代关系中，找出迭代（依赖链）次数最多的补丁版本。由于每个版本的前序版本（也就是“依赖它并发布新补丁”的版本）最多只有一个，这就意味着这些版本之间形成了多棵 树结构，每棵树的根节点即没有前序版本（输入中标记为 "NA" 的节点）。

本质问题：
对每棵树，从根节点出发，找出深度最大的叶子节点（即依赖链最长的版本）。如果有多个叶子节点的深度都相同，则按字典序输出所有这些版本。

解题思路

题目内容

某测试工具升级时总选择迭代次数最多的补丁版本，已知这些补丁版本的前序版本(即依赖该版本修改发布新补丁版本)，前序版本的个数$<=1$，且不会存在互为前序版本的情况。

请给出最终可以升级的补丁版本。版本号只包含大写字母和数字。

输入描述

第一行为记录的版本迭代关系个数$N$，范围是$[1,100000]$;

第二行到第$N+1$行:每行包含两个字符串，第一个字符串为当前版本，第二个字符串为前序版本，用空格隔开。字符串包含字符个数为$[1,100]$，没有前序版本的第二个字符串固定为$NA$

输出描述

输出所有迭代次数最多的补丁版本号字符串列表，多个版本号以字典序升序排列，用空格隔开

样例1

输入

6
CN0010 BF0001
BF0001 AZ0001
AZ0001 NA
BF0010 AZ0001
AW0001 NA
BF0011 AZ0001

输出

CN0010

说明

$AZ0001$和$AW0001$没有前序版本，各迭代了$0$次；

$BF0001，BF0010$和$BF0011$的前序版本为$AZO001$，各迭代了$1$次;

$CN0010$的前序版本为$BF0001，BF0001$的前序版本为$AZ0001$，迭代了$2$次。

根据要求选择迭代次数最多的补丁版本，因此输出$CN0010$。

样例2

输入

3
BF0001 AZ0001
AZ0001 NA
BF00011 AZ0001

输出

BF0001 BF00011

说明

$AZ0001$没有前序版本，迭代了$0$次;

$BF0001$和$BF00011$的前序版本为$AZ0001$，各迭代了$1$次;

根据要求选择迭代次数最多的补丁版本，有多个版本号时以字典序排列，因此输出$BF0001\ BF00011$