很喜欢，所以他给了你一棵个结点的树，要你求出：
上式中指和最近公共祖先的编号。所谓最近公共祖先，是指满足既是的祖先也是的祖先的深度最大的那个节点。我们认为节点自身也是自己的祖先。
树的结点从编号，根节点为号节点，答案对取模。
输入数据第一行仅一个正整数，含义如上所述。
接下来行，每行两个正整数代表从到连接有一条边。
仅一个正整数，为答案。
5 1 2 1 3 2 4 2 5
471