Cạnh trên Chu trình Đơn Duy nhất

Điểm: 8,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

C++, Dart, Go, Groovy, Java, Javascript, Kotlin, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Typescript, Zig

Cho một đồ thị vô hướng gồm $n$ đỉnh và $m$ cạnh. Đồ thị không nhất thiết liên thông, không chứa cạnh kép (không có nhiều hơn một cạnh giữa cùng một cặp đỉnh) và không chứa khuyên (cạnh nối một đỉnh với chính nó).

Một chu trình đơn trong đồ thị là một chu trình mà mỗi đỉnh xuất hiện đúng một lần trong chu trình đó.

Hãy xác định những cạnh thuộc về đúng một chu trình đơn của đồ thị.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $n$ và $m$ — số đỉnh và số cạnh.
$m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u$ và $v$ ( $1 \leq u, v \leq n$ , $u \neq v$ ) mô tả một cạnh nối đỉnh $u$ và $v$ . Các cạnh được đánh số từ $1$ theo thứ tự xuất hiện trong dữ liệu vào.

Dữ liệu ra

Dòng đầu in ra số lượng cạnh thuộc đúng một chu trình đơn.
Dòng thứ hai in ra chỉ số của các cạnh này theo thứ tự tăng dần, cách nhau bởi dấu cách. Nếu không có cạnh nào thoả mãn thì bỏ qua dòng này.

Ràng buộc

$1 \leq n \leq 100 000$
$0 \leq m \leq min (\frac{n (n - 1)}{2}, 100 000)$

Ví dụ

Input	Output	Giải thích
6 7 2 3 3 4 4 2 1 2 1 5 5 6 6 1	6 1 2 3 5 6 7	Đồ thị có hai tam giác rời nhau (đỉnh ${2, 3, 4}$ và ${1, 5, 6}$ — lưu ý cạnh $1 - 2$ là cầu, không nằm trong chu trình nào). Cả $6$ cạnh của hai tam giác đều thuộc đúng một chu trình đơn.
3 3 1 2 2 3 3 1	3 1 2 3	Cả ba cạnh tạo thành một tam giác — chu trình đơn duy nhất.
5 6 1 2 2 3 2 4 4 3 2 5 5 3	0	Đồ thị chứa nhiều chu trình đơn nhưng tất cả các cạnh đều được chia sẻ giữa ít nhất hai chu trình, nên không cạnh nào thuộc đúng một chu trình đơn.

Bình luận

Không có bình luận tại thời điểm này.