Xây dựng vùng LS Vagos

Xem PDF

Điểm: 300 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Sau khi đánh bại được Los Santos Vagos, thì nhóm CJ cũng tịch thu hẳn vùng đất của đối phương. Bây giờ, CJ sẽ xây dựng lại trật tự cũng như tập trung vài lực lượng chính vào vùng đất này. Ở vùng có \(N\) căn cứ và \(M\) tuyến đường hai chiều nối trực tiếp hai căn cứ, các căn cứ được đánh số từ \(1\) tới \(N\), và các tuyến đường cũng được đánh số từ \(1\) tới \(M\). CJ cử vài lực lượng quản lý các căn cứ và quyết định cử thêm người để canh gác những con đường. CJ đặc biệt quan tâm tới các con đường mà CJ cho con đường đó là rất quan trọng.

Tuyến đường quan trọng, theo định nghĩa của CJ là những tuyến đường mà khi gặp sự cố nguy hiểm (có thể bị phá hoặc bị chiếm) thì tập hợp các căn cứ mà có thể thông qua tuyến đường này thì sẽ bị chia thành hai phần và bất kì \(2\) căn cứ nào thuộc hai tập khác nhau đều không thể qua lại, yểm trợ nhau và tình thế của nhóm Grove Street Families (nhóm của CJ) sẽ gặp nguy hiểm.

Ví dụ bản đồ căn cứ của Los Santos Vagos (bây giờ đã là của Grove Street Families) như trên, khi tuyến đường \(4 - 3\) gặp sự cố nguy hiểm thì tập các căn cứ có thể thông qua tuyến đường \(4 - 3\) là (\(6\), \(4\), \(2\), \(3\), \(5\), \(1\)) bị chia ra \(2\) phần: (\(6\), \(4\)) và (\(2\), \(3\), \(5\), \(1\)) và bất kỳ \(2\) căn cứ thuộc \(2\) phần khác nhau, như \(6\)\(2\), đều không thể qua lại, yểm trợ nhau, nên \(4 - 3\) là tuyến đường quan trọng. Tuyến đường \(4 - 6\) cũng là tuyến đường quan trọng. Và tuyến đường \(1 - 5\) không phải là tuyến đường quan trọng.

Yêu cầu: Hãy chỉ ra cho CJ tất cả các tuyến đường quan trọng trên.

Input

  • Gồm \(M + 1\) dòng:
    • Dòng đầu tiên chứa hai số nguyên dương \(N\), \(M\) thể hiện số căn cứ và số tuyến đường hai chiều
    • \(M\) dòng tiếp theo, dòng thứ \(i\) chứa hai số \(u_i\)\(v_i\) thể hiện có tuyến đường hai chiều nối từ căn cứ \(u_i\) tới căn cứ \(v_i\)

Output

  • Ghi ra hai dòng:
    • Dòng đầu tiên ghi số \(K\) là số tuyến đường quan trọng.
    • Dòng tiếp theo là ghi ra số hiệu của \(K\) tuyến đường quan trọng tìm được theo thứ tự tăng dần.

Scoring

  • Subtask \(1\) (\(30\%\) số điểm): \(N \leq 10^3, M \leq 3.10^3\)
  • Subtask \(2\) (\(70\%\) số điểm): \(N \leq 10^5, M \leq 3.10^5\)

Example

Test 1

Input
6 6
1 3
1 5
2 3
3 4
3 5
4 6 
Output
3
3 4 6
Note

Giải thích: Đó là các tuyến đường \(2 - 3\) (có số hiệu là \(3\)), \(3 - 4\) (có số hiệu là \(4\)) và \(4 - 6\) (có số hiệu là \(6\)).


Bình luận

Không có bình luận nào.