P14906 [NHSPC 2024] 數字叢集

小明暑假期間在某實驗室實習，主要工作就是協助實驗室整理大量的實驗數據。 實驗室累積了許多數據資料，但因設備及管理等問題，小明發現有些數據可能登記錯誤； 這些記錯的數字**恰好為原數字的兩個位數被互換**， 例如數字 $1234$ 被記錄成 $1324$ 或者數字 $300$ 被記成 $3$ 等等。 小明希望你寫出一個程式檢查哪些資料有可能被登記錯誤，具體來說他定義了一個關係函式 $P(a, b)$， 若 $a$ 將某兩個位數互換後與 $b$ 相等，則 $P(a, b) = \text{True}$；否則 $P(a, b) = \text{False}$。 舉例來說 $P(300, 3) = \text{True}$， 因為 $300$ 的第一位數和第三位數互換時會變成 $3$； 但 $P(1234, 2143) = \text{False}$，因為交換任何兩個位數都無法變成相同的數字。 小明想要將 $n$ 個相異的非負整數 $a_1, a_2, \cdots a_n$ 運用關係函式 $P$ 來加以分群。 開始時，每一個數字可以自成一群， 對於一個數字 $x$ 和一個群 $S$， 如果 $S$ 有一個成員 $y$ 使得 $P(x, y) = \text{True}$， 則將 $x$ 所在的群與 $S$ 合併，形成更大的群。 小明想知道這些數據可以分成幾群，群的個數越小越好，和最大的群有多少數字。請寫一個程式幫助小明完成此任務。

$$\begin{aligned} &n \\ &a_1 \ a_2 \ \ldots \ a_n \end{aligned}$$ * $n$ 代表數字的個數。 * $a_i$ 代表第 $i$ 個想分群的整數。

$$G_n \quad G_m$$ * $G_n$ 代表分群後群的個數。 * $G_m$ 代表分群後最大的群有幾個數字。

### 測資限制 * $2 \le n \le 100$。 * $a_i$ 的位數小於等於 $5000$，$n$ 個數字皆相異且數字的前面不會有不必要的 $0$ (leading zero)。 * 輸入的數皆為非負整數。 ### 評分說明 本題共有三組子任務，條件限制如下所示。 每一組可有一或多筆測試資料，該組所有測試資料皆需答對才會獲得該組分數。 | 子任務 | 分數 | 額外輸入限制 | | :----: | :----------------: | --------------- | | 1 | 15 | $n \le 20$ 且 $a_i$ 的位數等於 $5$。 | | 2 | 28 | $a_i$ 的位數小於等於 $500$。 | | 3 | 57 | 無額外限制。 |