[USACO22FEB] Redistributing Gifts S

# 题目描述 FJ 有 $N$ 个礼物给他的 $N$ 头奶牛，这 $N$ 个礼物和 $N$ 头奶牛都被标记为 $1 \dotsm N (1 \le N \le 500)$ 。 每头奶牛都有一个愿望单，记录着一个含有 $N$ 个礼物的排列。比起在愿望单中出现更晚的礼物，奶牛更喜欢先出现在愿望单中的礼物。 因为 FJ 太懒了，他直接把 $i$ 号礼物分配给了 $i$ 号奶牛。现在，奶牛们聚在了一起，决定重新分配礼物，以便在重新分配后，每头奶牛都能得到跟原来一样，或是它更喜欢的礼物。 对于每个 $i$ （$i$ 从 $1$ 到 $N$），计算出重新分配后， $i$ 号奶牛可能拿到的最好的礼物（这个奶牛经过重新分配后能拿到的最喜欢的礼物）。 # 输入格式 第一行输入 $N$ 。之后 $N$ 行每行包含一个奶牛的愿望单。保证这 $N$ 行都是 $1 \dotsm N$ 的排列 # 输出格式 输出 $N$ 行，第 $i$ 行输出重新分配后 $i$ 号奶牛可能得到的最好礼物。 # 样例解释 在这个例子中，有两种可能的分配方案 - 最初的方案：一号奶牛得到一号礼物，二号奶牛得到二号礼物，三号奶牛得到三号礼物，四号奶牛得到四号礼物 - 重新分配后的方案：一号奶牛得到一号礼物，二号奶牛得到三号礼物，三号奶牛得到二号礼物，四号奶牛得到四号礼物。可以发现一号和四号奶牛都拿不到比FJ分配的更好的礼物。不过二号和三号都可以。 # 数据范围 - $2 \sim 3$ 号测试点满足 $N \le 8$ - $4 \sim 11$ 号测试点没有别的限制 由 [tzyt](https://www.luogu.com.cn/user/394488) 翻译

Farmer John has $N$ gifts labeled $1\cdots N$ for his $N$ cows, also labeled $1\cdots N$ $(1\le N\le 500)$. Each cow has a wishlist, which is a permutation of all $N$ gifts such that the cow prefers gifts that appear earlier in the list over gifts that appear later in the list. FJ was lazy and just assigned gift $i$ to cow $i$ for all $i$. Now, the cows have gathered amongst themselves and decided to reassign the gifts such that after reassignment, every cow ends up with the same gift as she did originally, or a gift that she prefers over the one she was originally assigned. For each $i$ from $1$ to $N$, compute the most preferred gift cow $i$ could hope to receive after reassignment.

The first line contains $N$. The next $N$ lines each contain the preference list of a cow. It is guaranteed that each line forms a permutation of $1\cdots N$.

Please output $N$ lines, the $i$-th of which contains the most preferred gift cow $i$ could hope to receive after reassignment.

4
1 2 3 4
1 3 2 4
1 2 3 4
1 2 3 4

1
3
2
4

【样例解释】 In this example, there are two possible reassignments: - The original assignment: cow 1 receives gift 1, cow 2 receives gift 2, cow 3 receives gift 3, and cow 4 receives gift 4. - Cow 1 receives gift 1, cow 2 receives gift 3, cow 3 receives gift 2, and cow 4 receives gift 4. Observe that both cows 1 and 4 cannot hope to receive better gifts than they were originally assigned. However, both cows 2 and 3 can. 【数据范围】 - Test cases 2-3 satisfy $N\le 8$. - Test cases 4-11 satisfy no additional constraints.