Giải bài trực tuyến

English

Vietnamese

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/flood

Năm 1964, một trận lụt khủng khiếp đã tràn vào thành vố Zagreb. Rất nhiều nhà cửa bị phá hủy khi nước tràn vào các bờ tường. Trong bài tập này, bạn được cho một mô hình đơn giản của thành phố trước trận lụt và bạn phải xác định xem các bức tường nào không bị đổ sau trận lụt.

Mô hình bao 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. Mô hình có thêm tính chất sau đây:

• Không có hai bức tường nào giao 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 tung hoặc trục hoành của mặt phẳng tọa độ.

Ban đầu, toàn bộ mặt phẳng tọa độ ở trạng thái khô. Vào thời điểm 0, nước lập tức tràn vào miền ngoài (phần không bị tường che chắn). Sau đúng một giờ, tất cả bức tường với một bên là nước, một bên là không khí sẽ bị vỡ dưới sức ép của nước. Nước sẽ tràn vào miền mới không bị chắn bởi bất kỳ bức tường nào. Và bây giờ có thể có những bức tường mới với một bên là nước, một bên là không khí.

Sau một giờ nữa, các bức tường này sẽ lại bị vỡ và nước sẽ tiếp tục tràn sâu hơn. Quá trình này tiếp diễn đến khi nước tràn vào toàn bộ khu vực.

Hình sau mô tả một ví dụ:

Trạng thái ở thời điểm 0.

Các ô được tô mô tả vùng bị lụt, trong khi các ô trắng mô tả vùng khô (chứa không khí).

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

Trạng thái sau hai giờ. Nước đã tràn vào toàn bộ thành phố và 4 bức tường còn lại không thể bị vỡ.

Yêu cầu

Viết chương trình, nhập vào tọa độ của N điểm và mô tả của W bức tường nối các điểm này, xác định xem bức tường nào còn đứng vững sao trận lụt.

Dữ liệu

Dòng đầu tiên của dữ liệu chứa một số nguyên N (2 <= N <= 100 000), số điểm trên mặt phẳng.

Mỗi dòng trong N dòng tiếp theo chứa 2 số nguyên X và Y (đều năm trong khoảng từ 0 đến 1,000,000), tọa độ của một điểm. Các điểm được đánh số từ 1 đến N theo thứ tự. Không có hai điểm nào nằm cùng một tọa độ.

Dòng tiếp theo chứa số nguyên W (1 <= W <= 2N), số bức tường.

Mỗi trong số W dòng sau chứa 2 số nguyên phân biệt A, B (1 <= A, B <= N), cho biết rằng trước trận lụt, có một bức tường nối giữa điểm A và B. Các bức tường được đánh số từ 1 đến W theo thứ tự.

Kết quả

Dòng đầu tiên chứa số nguyên K duy nhất, số bức tường còn đứng vững sau trận lụt. K dòng tiếp theo chứa chỉ số của các bức tường còn đứng vững; có thể in theo thứ tự bất kỳ.

Ví dụ

Dữ liệu
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

Kết quả
4
6
15
16
17