시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 312 63 32 17.877%

문제

전국 마라톤 대회가 개최될 예정이다. 몹시 큰 규모의 대회이므로 주최측에서는 등번호가 적힌 티셔츠를 일률적으로 배부하여 참가자들이 이를 입고 뛰게 한다.

이 티셔츠들은 양방향으로 뒤집어서 입을 수 있게 설계 되어 있다. 즉, 안쪽 면과 바깥쪽 면 모두에 등번호가 적혀있기 때문에 참가자들은 한 쪽 면을 선택하여 티셔츠를 입어야 한다.

문제는 티셔츠마다 고유한 등번호를 가지고 있는 것이 아니고, 또한 안쪽 면과 바깥쪽 면에 적힌 등번호가 서로 다르다는 것이다. 그래서 참가자들이 주의하지 않으면 서로 같은 등번호를 달고 뛰는 경우가 발생하게 된다.

이런 일이 발생하지 않도록, 참가자들에게 어떤 방향으로 옷을 입어야 하는지 알려주기 위한 프로그램을 작성하시오.

입력

첫째 줄에 티셔츠의 개수 N (1 ≤ N ≤ 1000000)이 주어진다. 이후 개의 행에 각 티셔츠의 정보가 두 개의 자연수로 주어진다. 이는 티셔츠의 안쪽과 바깥쪽에 적힌 등번호이다. 각 등번호는 1이상 1,000,000 이하이다.

출력

N개의 행에 각 셔츠별로, 밖으로 내보여야 할 등번호를 출력한다. 불가능한 경우에는 -1을 출력한다.

예제 입력

3
1 2
2 4
4 4

예제 출력

1
2
4

힌트

출처