문제
곧은 막대기를 세 개씩 가지고 있는 학생들이 모든 막대기를 바닥으로 던졌다.
각자 가지고 있던 막대기를 최대 한 개를 제거할 때, 바닥에 있는 나머지 막대기들이 서로 겹치지 않을 수 있는 지를 알아보기로 하였다.
단, 막대기가 제거될 때 다른 막대기의 위치는 변하지 않는다고 가정한다.
예를 들어, 학생 세 명이 각자 가지고 있는 막대기 ①②③, ④⑤⑥, ⑦⑧⑨를 바닥에 던진 막대기 모양이 아래와 같을 때,
막대기 한 개씩 ②, ④, ⑧을 제거하면 나머지 여섯 개의 막대기는 서로 겹치지 않게 된다.
바닥에 던져진 막대기의 양 끝점의 좌표가 주어졌을 때, 바닥에 남아 있는 막대기들이 서로 겹치지 않도록 각자 가지고 있던 막대기들 중에서 제거할 최대 한 개의 막대기를 찾는 프로그램을 작성하시오.
입력
첫째 줄에는 학생들의 수를 나타내는 정수 이 주어진다. N은 2 이상 1,000 이하이다.
두 번째 줄부터 3N개의 줄에는 한 줄에 막대기 한 개의 양 끝에 해당되는 두 끝점의 좌표를 나타내는 네 개의 정수 X1,Y1,X2,Y2가 빈칸을 사이에 두고 나타난다. 각 정수는 한 개의 막대기의 두 끝점의 좌표 (X1,Y1), (X2,Y2)를 나타낸다. 이 정수들은 -10,000 이상 10,000 이하이다.
두 번째 줄부터 나타나는 각 막대기는 1번부터 3N번까지 순서대로 번호가 부여되며, 연속적인 세 개의 번호 3i-2, 3i-1, 3i(1≤i≤N)는 i번째 학생이 가지고 있는 막대기 세 개의 번호를 나타낸다.
입력 데이터는 다음 세 조건을 항상 만족한다고 가정한다.
(조건 1) 막대기들의 끝점의 좌표가 같은 경우는 없다.
(조건 2) 세 개의 끝점이 임의의 일직선상에 위치하는 경우는 없다.
(조건 3) 세 개의 막대기가 한 점에서 만나는 경우는 없다.
출력
첫째 줄에는 서로 겹치지 않도록 막대기를 제거할 수 없는 경우에는 -1을 출력한다.
그렇지 않은 경우에는 첫째 줄에 제거된 막대기의 수인 K(0≤K≤N)를 출력한다. K가 최소일 필요는 없다.
두 번째 줄에는 제거된 막대기 K개의 번호를 빈칸을 사이에 두고 오름차순으로 출력한다.
단, K가 0인 경우에는 막대기 번호를 출력하지 않는다. 답이 여러 개인 경우에는 그 중 하나를 출력한다.
예제1
2
0696
5-185
153-1
5881
9000
1138
-1
예제2
3
38183175290
73142313247
190260213170
3823531225
17572293268
24024420182
70181192181
73282417142
19547388210
3
248