Định hướng từng cạnh của một đồ thị vô hướng liên thông để đồ thị có hướng thu được liên thông mạnh; nếu không tồn tại cách định hướng, in 0. Mỗi dòng hướng phải ứng với đúng cạnh cùng chỉ số trong input.
Input
Dòng đầu chứa n và m.
Mỗi trong m dòng tiếp theo chứa hai đầu mút của một cạnh vô hướng; cạnh thứ i xuất hiện ở dòng thứ i.
Output
Nếu không thể, in đúng một dòng chứa 0.
Nếu có thể, in m dòng; dòng i là ai bi, là hướng được chọn cho cạnh thứ i.
Constraints
2≤n≤105.
n−1≤m≤3⋅105.
Đồ thị liên thông, không có khuyên và không có cạnh trùng.
1≤u,v≤n.
Scoring
Subtask 1 (50% số điểm): n≤12vaˋm≤30.
Subtask 2 (50% số điểm): Không có giới hạn bổ sung.
Example
Test 1
Input
5 6
1 2
2 3
3 1
3 4
4 5
5 3
Output
1 2
2 3
3 1
3 4
4 5
5 3
Giải thích: Hai tam giác dùng chung đỉnh 3, nên không cạnh nào là cầu. Các hướng đã in tạo đường đi xuống theo cạnh cây và đường quay lại theo cạnh còn lại, vì vậy đồ thị có hướng liên thông mạnh.
Lời giải tóm tắt
Phân tích: DFS tính tin/low. Hướng cạnh cây từ cha xuống con, cạnh không thuộc cây từ đỉnh sâu hơn lên tổ tiên. Nếu có cạnh cây với low[con]>tin[cha] thì đó là cầu và bài toán vô nghiệm.
Thuật toán: DFS tính tin/low. Hướng cạnh cây từ cha xuống con, cạnh không thuộc cây từ đỉnh sâu hơn lên tổ tiên. Nếu có cạnh cây với low[con]>tin[cha] thì đó là cầu và bài toán vô nghiệm.
Chứng minh đúng: 1. Nếu có cầu, mọi hướng của cầu chỉ cho phép đi qua theo một chiều nên hai phía không thể đi tới nhau theo cả hai chiều. 2. Khi không có cầu, mỗi cây con DFS có một cạnh ngược đi tới cha hoặc một tổ tiên; kết hợp cạnh cây và cạnh ngược tạo đường từ cây con quay lên. 3. Gốc đi xuống mọi đỉnh qua cạnh cây, và mọi đỉnh quay về gốc; do đó mọi cặp đỉnh đi qua gốc theo hai chiều.