← 返回题目列表

Codeforces · 583/A

A. 柏油路

中文机器翻译题面 查看原题

城市X由n条垂直和n条水平的无限道路组成,形成n×n个交叉点。道路(垂直和水平)从 1 到 n 编号,交叉路口由形成它们的道路编号表示。

沙路早已被认为已经过时,因此决定铺设沥青。为此,我们聘请了一组工人并制定了工作计划,根据该计划,十字路口应铺设沥青。

道路维修计划为期 n2 天。在团队的第 i 天到达列表中的第 i 个交叉路口,如果形成交叉路口的两条道路都没有铺设沥青,则它们会为两条道路铺设沥青。否则,团队将离开十字路口,不对道路进行任何处理。

根据道路工程进度表,告知在哪几天至少有一条道路将被铺设沥青。

输入

第一行包含整数 n (1 ≤ n ≤ 50) — 城市中垂直和水平道路的数量。

接下来的 n2 行包含明细表中交叉点的顺序。其中第 i 个包含两个数字 hi、vi (1 ≤ hi, vi ≤ n),中间用空格隔开,表示时间表中第 i 条路口位于第 hi 条水平道路和第 vi 条垂直道路的交汇处。保证时间表中的所有路口都是不同的。

输出

在单行中按升序打印道路工程进行的天数。天数从 1 开始编号。

示例

输入 #1

2
1 1
1 2
2 1
2 2

输出 #1

1 4

输入 #2

1
1 1

输出 #2

1

注意

在样本中,该旅的行为如下:

1、第一天,大队来到第一横路和第一纵路的交汇处。由于都没有铺沥青,工人们就对第一条垂直路和第一条水平路进行了沥青铺设;
2. 第二天,工人大队来到第一横路和第二纵路的交汇处。第2条竖路还没有铺柏油,但由于第1条横路第一天就铺好了柏油,所以工人就离开了,没有铺柏油;
3. 第三天,工人们大队来到第二横路和第一纵路的交汇处。第二条水平路还没有铺沥青,但由于第一条垂直路第一天已经铺了沥青,工人就离开了,没有铺任何沥青;
4. 第四天,大队来到第二横路和第二纵路交叉口。由于都没有铺沥青,工人们就给第二条垂直路和第二条水平路铺了沥青。