In 2024, the city of Guadalajara will host the 1st Latin American Final of the ICPC. For this reason, the city government is interested in promoting tourism. They have collected information about the $$$N$$$ most important tourist attractions in the city. The mayor wants to organize these attractions into tourist circuits. A tourist circuit is a sequence of distinct tourist sites, say $$$\langle p_1, p_2, \ldots, p_\ell \rangle$$$ such that $$$\ell \geq 3$$$. Tourists participating in the circuit, starting at $$$p_1$$$, visit the attractions of the circuit following the sequence until they reach the site $$$p_\ell$$$. After visiting $$$p_\ell$$$, tourists return to $$$p_1$$$ to finish the circuit. Therefore, to form the circuit, there must be a street that connects tourist sites that are consecutive in the sequence (including $$$p_1$$$ and $$$p_\ell$$$).

The city government calculates that maintaining a circuit will have a high cost. Therefore, they want to divide the $$$N$$$ tourist sites into as few circuits as possible. In other words, they want to find a set of circuits such that each tourist site belongs to a unique circuit, and the set is as small as possible. To solve this difficult task, the city government hired Marcel "the optimizer" Saito.

Marcel received information about the city's street network. After an analysis, he realized that the network satisfies the following property. For any four tourist sites $$$A$$$, $$$B$$$, $$$C$$$ and $$$D$$$, $$$$$$ d(A, B) + d(C, D) \leq \max\{ d(A, C) + d(B, D), d(A, D) + d(B, C) \}, $$$$$$ where $$$d(U, V)$$$ is the smallest number of streets we need to travel to get from $$$U$$$ to $$$V$$$.

Marcel is sure that this property is important to solve the problem at hand. Unfortunately, he needs to take care of his newest apprentice Daniel "the dynamic" Ito. Therefore, he has entrusted this task to you, the newest trainee.