Tô màu vòng tròn

Cho một đồ thị có hướng $G$ gồm $n$ đỉnh và $m$ cung (cho phép có cung lặp và khuyên tự nối). Bạn cần tô mỗi đỉnh của đồ thị bằng một trong $k$ màu (với $k\le n$) sao cho: với mọi cung đi từ đỉnh $u$ tới đỉnh $v$, màu của đỉnh $v$ phải là màu kế tiếp của màu tô đỉnh $u$.

Các màu được đánh số vòng tròn từ $1$ tới $k$. Nghĩa là với mỗi màu $i$ ($i<k$), màu kế tiếp của nó là màu $i+1$; còn màu kế tiếp của màu $k$ là màu $1$. Đặc biệt, nếu $k=1$ thì màu kế tiếp của màu $1$ vẫn là màu $1$.

Nhiệm vụ của bạn là tìm và in ra giá trị $k$ lớn nhất có thể ($k\le n$) sao cho có thể tô màu đồ thị $G$ thỏa mãn điều kiện trên. Lưu ý rằng bạn không nhất thiết phải dùng hết cả $k$ màu (tức là không bắt buộc mỗi màu đều phải có đỉnh mang màu đó).

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$ là số đỉnh và số cung của đồ thị.
• $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a_i$ và $b_i$, cho biết cung thứ $i$ đi từ đỉnh $a_i$ tới đỉnh $b_i$.

Dữ liệu ra

In ra một số nguyên duy nhất, là số màu lớn nhất $k$ có thể dùng để tô đồ thị (thỏa $1\le k\le n$).

Ràng buộc

• $1\le n,m\le {10}^5$
• $1\le a_i,b_i\le n$
• Cho phép cung lặp và khuyên tự nối.

Ví dụ