Năm 1964, một trận lũ thảm khốc xảy ra tại Zagreb. Nhiều tòa nhà bị phá hủy hoàn toàn khi nước lũ đập vào các bức tường. Trong bài toán này, bạn được cho một mô hình đơn giản của thành phố trước trận lũ và cần xác định những bức tường còn nguyên sau khi lũ đi qua.

Mô hình gồm \(N\) điểm trên mặt phẳng tọa độ và \(W\) bức tường. Mỗi bức tường nối hai điểm và không đi qua bất kỳ điểm nào khác trong mô hình. Không có hai bức tường nào cắt nhau hoặc chồng lên nhau, nhưng chúng có thể chạm nhau tại các đầu mút. Mỗi bức tường song song với trục hoành hoặc trục tung.

Ban đầu, toàn bộ mặt phẳng đều khô ráo. Tại thời điểm \(0\), nước lập tức tràn ngập miền bên ngoài, tức là phần không gian không bị các bức tường bao kín. Sau đúng một giờ, tất cả những bức tường có một bên là nước và bên còn lại là không khí đồng thời bị phá vỡ do áp lực nước. Nước sau đó tràn vào những vùng mới không còn bị các bức tường đứng vững ngăn cách với bên ngoài.

Lúc này có thể xuất hiện những bức tường mới có một bên là nước, một bên là không khí. Sau một giờ nữa, những bức tường đó cũng bị phá vỡ và nước tiếp tục tràn vào. Quá trình lặp lại cho đến khi toàn bộ khu vực bị ngập.

Các hình dưới minh họa quá trình này. Phần tô màu là vùng ngập nước, còn phần trắng là vùng khô, chứa không khí.

Trạng thái tại thời điểm \(0\).

Trạng thái sau một giờ.

Trạng thái sau hai giờ. Nước đã tràn ngập toàn bộ khu vực và không thể phá vỡ \(4\) bức tường còn lại.

Hãy xác định các bức tường còn đứng vững sau trận lũ.

Dữ liệu vào

• Dòng đầu chứa số nguyên \(N\), là số điểm trên mặt phẳng.
• Mỗi dòng trong \(N\) dòng tiếp theo chứa hai số nguyên \(X,Y\), là tọa độ một điểm. Các điểm được đánh số từ \(1\) đến \(N\) theo thứ tự xuất hiện trong dữ liệu vào. Không có hai điểm trùng tọa độ.
• Dòng tiếp theo chứa số nguyên \(W\), là số bức tường.
• Mỗi dòng trong \(W\) dòng tiếp theo chứa hai số nguyên khác nhau \(A,B\), mô tả một bức tường nối điểm \(A\) với điểm \(B\) trước trận lũ. Các bức tường được đánh số từ \(1\) đến \(W\) theo thứ tự xuất hiện trong dữ liệu vào.

Dữ liệu ra

Dòng đầu chứa một số nguyên \(K\), là số bức tường còn đứng vững sau trận lũ.

\(K\) dòng tiếp theo chứa chỉ số của các bức tường đó, mỗi dòng một chỉ số. Có thể xuất các chỉ số theo thứ tự bất kỳ.

Ràng buộc

• \(2\le N\le 100\,000\).
• \(0\le X,Y\le 1\,000\,000\).
• \(1\le W\le 2N\).
• \(1\le A,B\le N\) và \(A\ne B\).
• Các điểm và bức tường thỏa mãn mọi điều kiện hình học đã nêu trong mô tả.

Chấm điểm trên hệ thống

Lưu ý: Cách chia nhóm và tính điểm dưới đây là bản điều chỉnh để luyện tập trên hệ thống, không khẳng định tương đương cách chấm tại IOI gốc.

Mỗi nhóm được chấm độc lập: chỉ nhận điểm của nhóm khi vượt qua tất cả bộ kiểm thử trong nhóm; nếu có bộ kiểm thử không đạt thì nhóm nhận 0 điểm. Tổng điểm tối đa là 100.

Nhãn nhóm là phần số trong tên tệp dữ liệu gốc. Tất cả tệp cùng nhãn, kể cả các hậu tố chữ và pf, đều thuộc nhóm đó.

Các ví dụ trong đề không tính điểm.

Ví dụ

15
1 1
8 1
4 2
7 2
2 3
4 3
6 3
2 5
4 5
6 5
4 6
7 6
1 8
4 8
8 8
17
1 2
2 15
15 14
14 13
13 1
14 11
11 12
12 4
4 3
3 6
6 5
5 8
8 9
9 11
9 10
10 7
7 6

4
6
15
16
17

Nguồn

IOI 2007.