전깃줄 2

두 전봇대 A와 B 사이에 여러 개의 전깃줄이 연결되어 있다. 서로 다른 두 전깃줄이 교차하면 합선 위험이 있으므로, 일부 전깃줄을 제거해서 남은 전깃줄이 서로 교차하지 않게 하려고 한다.

아래 그림처럼 전깃줄이 연결되어 있을 때, A 전봇대의 1번 위치와 B 전봇대의 8번 위치를 잇는 전깃줄, A 전봇대의 3번 위치와 B 전봇대의 9번 위치를 잇는 전깃줄, A 전봇대의 4번 위치와 B 전봇대의 1번 위치를 잇는 전깃줄을 제거하면 남은 전깃줄들은 서로 교차하지 않는다.

<그림 1>

전깃줄이 전봇대에 연결되는 위치는 위에서부터 차례대로 번호가 매겨진다. 전깃줄의 개수와 각 전깃줄이 두 전봇대에 연결되는 위치 번호가 주어질 때, 모든 교차를 없애기 위해 제거해야 하는 전깃줄의 최소 개수와 제거할 전깃줄의 A 전봇대 위치 번호를 구하라.

첫째 줄에 두 전봇대 사이에 연결된 전깃줄의 개수 N이 주어진다. N은 100,000 이하의 자연수이다.

둘째 줄부터 N개의 줄에는 각 전깃줄이 A 전봇대와 연결되는 위치 번호와 B 전봇대와 연결되는 위치 번호가 차례로 주어진다. 위치 번호는 500,000 이하의 자연수이며, 같은 전봇대의 같은 위치에 두 개 이상의 전깃줄이 연결되는 경우는 없다.

첫째 줄에 남은 모든 전깃줄이 서로 교차하지 않도록 만들기 위해 제거해야 하는 전깃줄의 최소 개수를 출력한다.

둘째 줄부터 제거해야 하는 전깃줄의 A 전봇대 위치 번호를 한 줄에 하나씩 오름차순으로 출력한다. 가능한 답이 여러 가지라면 그중 아무 하나를 출력한다.