Phân Vùng Tương Hỗ

Chia các đỉnh của một đồ thị có hướng thành những nhóm cực đại sao cho hai đỉnh cùng nhóm khi và chỉ khi mỗi đỉnh đi tới được đỉnh kia; in số nhóm và nhãn của từng đỉnh. Các số nhãn không cần trùng với một cách đánh số cố định; chỉ phân hoạch các đỉnh phải đúng.

Input

• Dòng đầu chứa $n$ và $m$.
• Mỗi trong $m$ dòng tiếp theo chứa một cung $u$ $v$, hướng từ $u$ đến $v$.

Output

• Dòng đầu in số thành phần liên thông mạnh $k$.
• Dòng thứ hai in $n$ nhãn; nhãn nằm trong $[1,k]$, và hai đỉnh có cùng nhãn khi và chỉ khi thuộc cùng một thành phần liên thông mạnh.

Constraints

• $1\le n\le 10^5.$
• $0\le m\le 2\cdot 10^5.$
• $1\le u,v\le n.$

Scoring

• Subtask $1$ ($50\%$ số điểm): $n\le 12\text{vaˋ}m\le 40$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

6 7
1 2
2 3
3 1
3 4
4 5
5 4
5 6

3
1 1 1 2 2 3