302995: CF583A. Asphalting Roads

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Asphalting Roads

题意翻译

### 题目描述 有一个边长为$n$的正方形的城市,一个小组要在这个城市的路上铺上柏油路。一共要进行$n^2$天,小组第$i$天要铺两条道路$h_i$和$v_i$。如果当天要铺的两条路道路都没被铺过则将这两条道路铺上柏油路,否则则什么都不干。根据施工的时间表,告诉这条道路将在哪几天里被铺上柏油路。 ### 输入格式 第一行一个数n$(1<=n<=50)$,表示城市的边长 接下来的$n^2$行每行两个数,表示$h_i$和$v_i$$(1<=h_i,v_i<=n) $ ### 输出格式 一行若干个数,哪几天里会被铺上柏油路(天数从1开始算) #### Translate by @zky06

题目描述

City X consists of $ n $ vertical and $ n $ horizontal infinite roads, forming $ n×n $ intersections. Roads (both vertical and horizontal) are numbered from $ 1 $ to $ n $ , and the intersections are indicated by the numbers of the roads that form them. Sand roads have long been recognized out of date, so the decision was made to asphalt them. To do this, a team of workers was hired and a schedule of work was made, according to which the intersections should be asphalted. Road repairs are planned for $ n^{2} $ days. On the $ i $ -th day of the team arrives at the $ i $ -th intersection in the list and if none of the two roads that form the intersection were already asphalted they asphalt both roads. Otherwise, the team leaves the intersection, without doing anything with the roads. According to the schedule of road works tell in which days at least one road will be asphalted.

输入输出格式

输入格式


The first line contains integer $ n $ ( $ 1<=n<=50 $ ) — the number of vertical and horizontal roads in the city. Next $ n^{2} $ lines contain the order of intersections in the schedule. The $ i $ -th of them contains two numbers $ h_{i},v_{i} $ ( $ 1<=h_{i},v_{i}<=n $ ), separated by a space, and meaning that the intersection that goes $ i $ -th in the timetable is at the intersection of the $ h_{i} $ -th horizontal and $ v_{i} $ -th vertical roads. It is guaranteed that all the intersections in the timetable are distinct.

输出格式


In the single line print the numbers of the days when road works will be in progress in ascending order. The days are numbered starting from $ 1 $ .

输入输出样例

输入样例 #1

2
1 1
1 2
2 1
2 2

输出样例 #1

1 4 

输入样例 #2

1
1 1

输出样例 #2

1 

说明

In the sample the brigade acts like that: 1. On the first day the brigade comes to the intersection of the 1-st horizontal and the 1-st vertical road. As none of them has been asphalted, the workers asphalt the 1-st vertical and the 1-st horizontal road; 2. On the second day the brigade of the workers comes to the intersection of the 1-st horizontal and the 2-nd vertical road. The 2-nd vertical road hasn't been asphalted, but as the 1-st horizontal road has been asphalted on the first day, the workers leave and do not asphalt anything; 3. On the third day the brigade of the workers come to the intersection of the 2-nd horizontal and the 1-st vertical road. The 2-nd horizontal road hasn't been asphalted but as the 1-st vertical road has been asphalted on the first day, the workers leave and do not asphalt anything; 4. On the fourth day the brigade come to the intersection formed by the intersection of the 2-nd horizontal and 2-nd vertical road. As none of them has been asphalted, the workers asphalt the 2-nd vertical and the 2-nd horizontal road.

Input

题意翻译

### 题目描述 有一个边长为$n$的正方形的城市,一个小组要在这个城市的路上铺上柏油路。一共要进行$n^2$天,小组第$i$天要铺两条道路$h_i$和$v_i$。如果当天要铺的两条路道路都没被铺过则将这两条道路铺上柏油路,否则则什么都不干。根据施工的时间表,告诉这条道路将在哪几天里被铺上柏油路。 ### 输入格式 第一行一个数n$(1<=n<=50)$,表示城市的边长 接下来的$n^2$行每行两个数,表示$h_i$和$v_i$$(1<=h_i,v_i<=n) $ ### 输出格式 一行若干个数,哪几天里会被铺上柏油路(天数从1开始算) #### Translate by @zky06

加入题单

上一题 下一题 算法标签: