Một hệ thống giao thông gồm có N nút giao thông đánh số từ 1 đến N và M đường hai chiều nối một số cặp nút, không có hai đường nối cùng một cặp nút. Hệ thống đảm bảo đi lại giữa hai hút bất kì. Để đảm bảo an toàn, người ta quyết định rằng các đường hai chiều trước đây nay sẽ thành một chiều, và vấn đề ở chỗ chọn chiều cho mỗi đường như thế nào.

Hãy tìm cách định hướng các cạnh sao cho hệ thống vẫn đảm bảo đi lại giữa hai cặp nút bất kì.

INPUT

• Dòng đầu ghi hai số nguyên dương N, M (1 <= N <= 50000 , 1 <= M <= 100000).

• M dòng tiếp theo, mỗi dòng thể hiện một đường hai chiều gồm u, v là chỉ số hai nút mà nó nối tới .

OUTPUT

• Dòng đầu ghi 1/0 tương ứng với có tìm được phương án thoả mãn hay không .

• Nếu có, M dòng tiếp theo mỗi dòng thể hiện sự định hướng một cạnh bao gồm hai số u, v với ý nghĩa định hướng cạnh (u,v) thành đường một chiều từ u đến v.

Sample Input

4 5
1 2
2 3
2 4
3 4
1 4

Sample Output

1
1 2
2 3
2 4
3 4
4 1

Sample Input

4 4
1 2
2 3
3 4
3 1

Sample Output

0