一大堆題目上線嘍 熱騰騰剛搬完的 2024 上機考、終局之戰、2025 小社賽和上機考都上線了，歡迎大家幫忙驗題，然後一五該請我拉麵了 --- by AaW
4621 . Finite State Machine
Description
不是啊 她又不喜歡我 我也不喜歡她
— 溫室羊, 建資百十五學術
「不要靠邀 一週內暈船我好強」一週後他如此說道，正如同溫室羊的暈船轉換過程，有限狀態機（Finite-State Machine，簡稱 FSM）是 腦癱大學(NauTan University) Emo Everyday 學系（簡稱 NTUEE）大一必修課之一 交換電路與邏輯設計 的重點概念之一。其中一種常見的有限狀態機稱之為 Mealy Machine，其特點是輸出由當前 State 和當前輸入共同決定。每個狀態會根據當前的輸入選擇對應的狀態轉移，同時生成相應的輸出。因此，輸出是即時更新的，隨著輸入的改變而變化。
一個 Mealy Machine 可以用一張 State Table 來表示。如下圖所示，表中一橫列代表一個 State ，當機器處於某 Present State 且接收到輸入 $x$ 時，將生成輸出 $z$ ，並在下一個時間點轉移到 Next State。
State table.
我們可以注意到，若一個有限狀態機有 $N$ 個狀態（State），則至少需要 $\lceil \log_2 N \rceil$ 個位元來表示每個狀態。然而，在 CPU 中儲存每個位元所需的電晶體成本相當高昂，因此我們需要對狀態進行化簡以降低資源消耗。
我們將兩個狀態定義為「等價」，若且唯若它們在所有可能的輸入（Input）下具有相同的輸出（Output），且其對應的下一狀態（Next State）也指向相同的等價狀態。例如，上表中的 $S_5$ 和 $S_8$ 即為等價狀態。
化簡狀態的第一步驟是識別所有等價的狀態，並將它們合併為單一狀態，從而減少狀態數量，提升有限狀態機的效率。
同時，在上表當中，
$S_0 = S_3$ 若且唯若 $S_3 = S_0$ 且 $S_2 = S_4$，
$S_2 = S_4$ 若且唯若 $S_4 = S_2$ 且 $S_3 = S_0$，
因為這兩個條件句無矛盾，所以 $S_0 = S_3$ 和 $S_2 = S_4$ 同時成立。因此，這張表最後可以化簡為 6 個 State。
上述做法可以使用稱之為 Implication Table 的方式完成。如下圖所示，先將每個 State 要相同的條件寫在表格中，並且將絕對不可能的情況打叉（例如 Output 不同的兩個 State）。之後，不斷地檢查每一個條件是否已經無法達成了，若無法達成就打叉，直到表中每一格都無法被打叉為止，剩下每一個沒被打叉的格子就代表一組 State 相等。
Implication table.
上面這一坨化簡的方式，Aaron Wu 完全都看不懂。因此，他打算找另一個 Aaron Wu 幫忙，請他寫一個程式，只要輸入一整張 State Table，就會輸出哪些 State 相等。然而，另一個 Aaron Wu 忙著在處理脆上的公關危機，因此，你能幫助 Aaron Wu 們完成這份程式嗎？
Input Format
第一行有兩個正整數 $n, m$ ($2\le n \le 1000,\ 2\le m \le 16$) "--- State 的數量和可能的 Output 數。
接下來 $n$ 行，每行有 $m$ 個整數 $q_{ij}$ ($0\le q_{ij} < n$) "--- 當狀態為 $S_i$，input 為 $j$ 時，會在下一個時間轉為 $S_{q_{ij}}$
接下來 $n$ 行每行有 $m$ 個整數 $z_{ij}$ ($0\le z_{ij} \le 1$) "--- 當狀態為 $S_i$，input 為 $j$ 時，FSM 會 Output $z_{ij}$
Output Format
請輸出若干行，每行兩個整數 $a < b$，代表 $S_a = S_b$。
若無任何 State 相等，請輸出 Emo Everyday
另外，請排序後再輸出（詳見範例1）
Sample Input 1
5 2 1 4 1 4 2 0 1 4 2 0 0 0 0 0 1 0 0 0 1 0
Sample Output 1
0 1 0 3 1 3 2 4
Sample Input 2
9 2 3 2 8 7 4 3 0 4 2 0 5 1 1 7 2 6 5 1 0 1 0 1 1 0 0 1 1 0 1 0 0 1 1 0 1 0
Sample Output 2
0 3 2 4 5 8
Sample Input 3
2 4 0 1 0 1 1 0 1 0 0 0 0 1 1 1 0 1
Sample Output 3
Emo Everyday
Hints
說明文章： https://reurl.cc/74VX0y
對於 Sample 1，State Table 如下所示，可見 $S_0 = S_1 = S_3, \quad S_2 = S_4$
對於 Sample 3，State Table 如下所示，可見 $S_0$ 和 $S_1$ Output 不同，因此無法化簡
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~9 | $n \le 10$ | 14 |
| 2 | 10~19 | 保證不等價的 state 都有不同的 output | 8 |
| 3 | 0~39 | 無其他限制 | 78 |