灰灰的火车

灰灰的火车

出题人太菜,暂无测试数据。

题目描述

灰灰从名飞那里搞到了很多节火车,每节火车都可以作为车头或中间车厢或车尾。第\(i\)节火车的头尾各有两个属性值\(h_i\)与\(t_i\)。两节火车\(i\)与\(j\)可以拼接,当且仅当\(t_i = h_j\)。拼接后的火车\(ij\)的属性值分别为\(h_i\)与\(t_j\)。且火车的节数\(w_{ij} = w_i + w_j\)。第\(i\)节火车的初始节数\(w_i = 1\)。
现在灰灰和名飞玩一种游戏。对于\(N\)节火车,要求灰灰拼接他们, 直到无法拼接 。使得最终火车中节数最小的火车在所有的合并方案中节数最小的火车中最大。

输入输出格式

输入格式

第一行一个正整数\(N\),代表初始有几节火车
接下来的\(N\)行每行两个整数\(h, t\)

输出格式

输出最终最小\(w\)的最大值

样例

输入

4
1 2
2 3
3 4
2 4

输出

2

数据范围

测试点编号 特殊性质
1~2 保证所有\(h_i, t_i\)互不相同
3~5 \(N, h_i, t_i \leqslant 100\)
6~8
9~10 \(t_i = h_i + 1\)

对于所有数据,保证\(N, h_i, t_i \leqslant 10000\)

信息

ID
1037
难度
(无)
分类
(无)
标签
递交数
0
已通过
0
通过率
?
上传者

相关

在下列训练计划中:

灰灰的通天塔 | Huihui‘s Babel