换乘旅行
题目描述
小明来到了一座著名的旅游城市，这座城市有一个包含\(n\)个站点的公共交通网络。该网络的运行方式非常独特。每个站点\(i\)都有一个按顺序排列的摆渡车出发队列。每辆摆渡车都有一个固定的、预先设定的目的地站点。一位旅客的行程如下：每当他到达一个站点（无论是起点还是中途换乘），他都必须搭乘该站点队列中最靠前的一辆摆渡车，这辆车会将他送到其目的地，然后不再运行。到达新站点后，他会继续按相同规则搭乘下一辆车。当旅客到达一个没有任何待出发车辆的站点时，他的旅程就结束了，该站点即为他的最终目的地。这些站点排成一排，从左到右依次编号为\(1\)到\(n\)。小明想要知道，对于每一个站点，如果从它出发，最终会到达哪里。
输入格式
从文件\(travel.in\)中读入数据。
第一行包含一个整数\(n\),表示站点的数量。
接下来\(n\)行，第\(i\)行描述了第\(i\)个站点的摆渡车队列信息。
• 行首是一个整数\(k_i\),表示站点 i 的队列中有\(k_i\)辆摆渡车。
• 随后是\(k_i\)个整数\(d_{i,1},d_{i,2},...,d_{i,k_i}\),按出发顺序列出了每辆车的目的地。\(d_{i,1}\)是第一辆出发的车的目标站,\(d_{i,2}\)是第二辆,以此类推。
输出格式
输出到文件\(travel.out\)中。
输出\(n\)行：
第\(i\)行包含一个整数，表示从站点\(i\)开始旅行的最终站点的编号。
输入输出样例
输入 #1
3
3 1 2 2
3 3 1 2
3 1 2 1
输出 #1
1
2
2
输入 #2
5
5 1 2 4 3 4
6 1 2 5 3 3 4
6 1 1 4 4 4 2
9 3 1 4 2 3 5 5 1 2
4 4 4 1 3
输出 #2
1
1
1
1
1
子任务
对于所有数据，保证：
• \(1≤n≤10^5\)
•\(0≤k_i≤10^5\)
• \(\sum_{i=1}^{n}k_i≤10^6\)
• \(1≤d_{i,j}≤n\)
| 测试点 | \(n\) | \(\sum_{i=1}^nk_i\) | 附加限制 |
|---|---|---|---|
| 1~4 | \(≤1000\) | \(≤1000\) | 无 |
| 5~7 | \(≤10^5\) | \(≤10^5\) | \(k_i=1\) |
| 8~10 | \(≤10^5\) | \(≤10^6\) | 无 |