World Map

문제

Mr. Pacha, a Bolivian archeologist, discovered an ancient document near Tiwanaku that describes the world during the Tiwanaku Period (300-1000 CE). At that time, there were $NN$ countries, numbered from $11$ to $NN$.

In the document, there is a list of $MM$ different pairs of adjacent countries: $$(A[0],B[0]),(A[1],B[1]),\dots ,(A[M-1],B[M-1])\mathrm{.}(A[0],\; B[0]),\; (A[1],\; B[1]),\; \backslash ldots,\; (A[M-1],\; B[M-1]).$$ For each $ii$ (), the document states that country $A[i]A[i]$ was adjacent to country $B[i]B[i]$ and vice versa. Pairs of countries not listed were not adjacent.

Mr. Pacha wants to create a map of the world such that all adjacencies between countries are exactly as they were during the Tiwanaku Period. For this purpose, he first chooses a positive integer $KK$. Then, he draws the map as a grid of $K\times KK\; \backslash times\; K$ square cells, with rows numbered from $00$ to $K-1K\; -\; 1$ (top to bottom) and columns numbered from $00$ to $K-1K\; -\; 1$ (left to right).

He wants to color each cell of the map using one of $NN$ colors. The colors are numbered from $11$ to $NN$, and country $jj$ ($1\le j\le N1\; \backslash leq\; j\; \backslash leq\; N$) is represented by color $jj$. The coloring must satisfy all of the following conditions:

• For each $jj$ ($1\le j\le N1\; \backslash leq\; j\; \backslash leq\; N$), there is at least one cell with color $jj$.
• For each pair of adjacent countries $(A[i],B[i])(A[i],\; B[i])$, there is at least one pair of adjacent cells such that one of them is colored $A[i]A[i]$ and the other is colored $B[i]B[i]$. Two cells are adjacent if they share a side.
• For each pair of adjacent cells with different colors, the countries represented by these two colors were adjacent during the Tiwanaku Period.

For example, if $N=3N\; =\; 3$, $M=2M\; =\; 2$ and the pairs of adjacent countries are $(1,2)(1,2)$ and $(2,3)(2,3)$, then the pair $(1,3)(1,3)$ was not adjacent, and the following map of dimension $K=3K\; =\; 3$ satisfies all the conditions.

In particular, a country does not need to form a connected region on the map. In the map above, country 3 forms a connected region, while countries 1 and 2 form disconnected regions.

Your task is to help Mr. Pacha choose a value of $KK$ and create a map. The document guarantees that such a map exists. Since Mr. Pacha prefers smaller maps, in the last subtask your score depends on the value of $KK$, and lower values of $KK$ may result in a better score. However, finding the minimum possible value of $KK$ is not required.