Team Partitioning Based on Acquaintance Graph

K Country is famous for its love of triangles. In this country, only triangular relationships are appreciated. A triangle relationship means that for any three persons A, B, and C, A knows B, B knows C, and C knows A. In order to promote these simple and efficient relationships, K Country forbids any pure N-gon relationship for any N > 3.

A pure N-gon relationship is defined as follows: For N persons \(A_1, A_2, ..., A_N\), there are exactly N mutual acquaintance pairs: \( (A_1,A_2), (A_2,A_3), ..., (A_N,A_1) \) and no other acquaintance exists among these N persons. For example, in a 4-gon relationship among persons A, B, C, and D, only the pairs (A,B), (B,C), (C,D) and (D,A) are acquainted, while pairs (A,C) and (B,D) are not.

During the national contest, to prevent collusion, the rule is that any two persons who know each other cannot be in the same team. Given a network of acquaintances that complies with the country’s restriction (i.e. no pure N-gon exists for N > 3), determine the minimum number of teams required. This number is exactly the chromatic number of the given acquaintance graph.

Note: Since the graph does not contain any induced cycle of length \( N \ge 4 \) (pure N-gon), it is a chordal graph. In chordal graphs, the chromatic number is equal to the size of the maximum clique.

inputFormat

The first line contains two integers \(n\) and \(m\) (\(1 \leq n \leq 10^5\), \(0 \leq m \leq 10^5\)), denoting the number of persons and the number of acquaintance pairs respectively.

Each of the next \(m\) lines contains two integers \(u\) and \(v\) (\(1 \le u, v \le n, u \neq v\)), indicating that person \(u\) and person \(v\) know each other. The acquaintance relation is bidirectional.

It is guaranteed that the acquaintance network follows K Country's rule (i.e. no pure N-gon relationship exists for any \(N > 3\)).

outputFormat

Output a single integer: the minimum number of teams required such that no two persons who know each other are on the same team.

sample

3 3
1 2
2 3
3 1

3