404390: GYM101492 G Splitting the Empire

Carlitos "Curious" Nunes is studying the history of China at school. More specifically, he is studying the times known as the "Golden Age" of China. The History exam is soon to come and he decided to write some notes to help his studies. He wrote:

The Golden Age (600–1,600AD) is a period of history when China was ruled by the Tang (618–906AD) and Song (960–1,279AD) dynasties. It is characterized by the end of internal wars and by enormous commercial and technological development (tea, explosives, the compass, and printing).

Growth in commerce took place during the rule of the Song dynasty. To stimulate the exchange of goods among cities, Emperor Taizu Song built many roads joining the cities of the empire. On the one hand, one could reach any city from any other city using these roads. On the other hand, there were so many roads that people believed the following to hold: for any four cities, say A, B, C, and D,

where d(U, V) is the smallest number of roads needed to go from U to V.

The Golden Age ended when the Mongols invaded China in 1,279AD and established the Yuan dynasty.

Genghis Khan, fearing a Chinese uprising, split the cities of the empire among his army commanders. The split up was performed so that each commander was responsible for a subset of cities such that no two of these cities was joined by a road. Furthermore, each city belonged to precisely one commander.

Carlitos is very curious to find how Genghis Khan could have made such a split, and how many commanders his army should have so that the split was possible. Carlitos wants to solve this puzzle before leaving for his vacation at Foz de Iguaçu. Can you help him?

The first line has two integers, N and M, the number of cities and roads in the Chinese empire, respectively. The M lines that follow each contain two integers, u and v, the cities joined by one road. There are no two roads joining the same pair of cities.

• 1 ≤ N ≤ 5·10⁴
• 2 ≤ M ≤ 5·10⁵
• 1 ≤ u, v ≤ N, u ≠ v

Print an integer, the minimum number of commanders required to split up the empire.

3 3
1 2
1 3
2 3

3

5 4
1 2
1 3
1 4
1 5

2