## Problem
作為邪惡聯盟 (Evil League of Evil) 的領導者，壞馬 (Bad Horse) 需要處理很多問題。最近，聯盟內部有太多的爭吵和背叛，因此壞馬決定將聯盟分成兩個部門，以分開那些彼此仇視的成員。作為罪惡的純種馬 (Thoroughbred of Sin)，壞馬不會花費寶貴的時間自己來解決如何分割聯盟成員的問題。這就是為什麼他需要你 —— 他忠實的手下 —— 來完成這項任務。

## Input
輸入的第一行給出了測資的數量 **T**。接下來是 **T** 個測資。每個測資以一個正整數 **M** 開頭 —— 這是仇人對的數量。接下來的 **M** 行，每行包含一對成員的名字，名字之間用一個空格分隔。

## Output
對於每個測資，輸出一行 `Case #x: y`，其中 `x` 是測資的編號 (從 1 開始)，`y` 是 `Yes` 或 `No`，表示能否將聯盟成員分成兩組，使得沒有一組包含仇人對。

## Limits
* 每個測資組的時間限制：60 秒。
* 每個測資組的記憶體限制：1 GB。
* $1 \le$ **T** $\le 100$。
* 每個成員名字只包含字母和底線字元。
* 名字區分大小寫。
* 同一測資中不會出現重複的成員對。
* 每個成員對中都有兩個不同的成員。

### Small dataset
$1 \le$ **M** $\le 10$。

### Large dataset
$1 \le$ **M** $\le 100$。

## Sample
#### Sample Input

2
1
Dead_Bowie Fake_Thomas_Jefferson
3
Dead_Bowie Fake_Thomas_Jefferson
Fake_Thomas_Jefferson Fury_Leika
Fury_Leika Dead_Bowie

#### Sample Output

Case #1: Yes
Case #2: No

---

在第一筆測資中，只有一對仇人，因此我們只需要將其直接分開即可：

| Group A | Group B |
|:-------:|:-------:|
| Dead Bowie | Fake Thomas Jefferson |

因此輸出 `Yes`。

---

在第二筆測資中，我們先將第一對仇人分開：

| Group A | Group B |
|:-------:|:-------:|
| Dead Bowie | Fake Thomas Jefferson |

接著考慮第二對仇人，其中的 `Fake_Thomas_Jefferson` 已被分到了 **Group B** ，因此他的仇人 `Fury_Leika` 就必須被分到 **Group A**：

| Group A | Group B |
|:----------:|:---------------------:|
| Dead Bowie | Fake Thomas Jefferson |
| Fury Leika | |

最後考慮第三對仇人，會發現 `Fury_Leika` 和 `Dead_Bowie` 互為仇人，但是他們卻已被分到了同一組。因此無論怎麼分都無法將所有的「仇人對」都分開，輸出 `No`。

## Datasets
#### Small dataset
* [Input Raw](https://raw.githubusercontent.com/google/coding-competitions-archive/main/kickstart/2013/practice_round/bad_horse/data/secret/subtask1/1.in)
* [Output Raw](https://raw.githubusercontent.com/google/coding-competitions-archive/main/kickstart/2013/practice_round/bad_horse/data/secret/subtask1/1.ans)

#### Large dataset
* [Input Raw](https://raw.githubusercontent.com/google/coding-competitions-archive/main/kickstart/2013/practice_round/bad_horse/data/secret/subtask2/1.in)
* [Output Raw](https://raw.githubusercontent.com/google/coding-competitions-archive/main/kickstart/2013/practice_round/bad_horse/data/secret/subtask2/1.ans)

## Solution
:::spoiler Editorial (C++17)

### Algorithm
要解決這個問題，我們需要判斷是否可以將邪惡聯盟的成員分成兩組，使得任何一對仇人 (在輸入中給出) 不在同一組中。這實際上是一個二分圖 (bipartite graph) 問題。如果可以用兩種顏色對圖進行著色，使得沒有兩個相鄰的節點 (在我們的情況下是成員) 具有相同的顏色，則該圖是二分圖。

以下是解決這個問題的逐步計劃：
1. **讀取輸入**：讀取測資的數量。
2. **對於每個測資**：
* 讀取仇人對的數量。
* 讀取每對仇人成員並構建圖。
3. **檢查是否為二分圖**：
* 使用 BFS (廣度優先搜索) 嘗試用兩種顏色對圖進行著色。
* 如果發現衝突 (即兩個相鄰的節點具有相同的顏色)，則該圖不是二分圖。
4. **輸出結果**：對於每個測資，輸出 `Yes` 如果圖是二分圖，否則輸出 `No`。

### Implementation

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <string>

using namespace std;

bool isBipartite(vector<pair<string, string>> &pairs) {
    unordered_map<string, vector<string>> graph;
    unordered_map<string, int> color;

    // Build the graph
    for (const auto& p : pairs) {
        graph[p.first].push_back(p.second);
        graph[p.second].push_back(p.first);
    }

    // BFS to check bipartiteness
    for (const auto& node : graph) {
        if (color.find(node.first) == color.end()) { // not colored yet
            queue<string> q;
            q.push(node.first);
            color[node.first] = 0; // Start coloring with 0

            while (!q.empty()) {
                string u = q.front();
                q.pop();

                for (const string& v : graph[u]) {
                    if (color.find(v) == color.end()) {
                        // Color with opposite color
                        color[v] = color[u] ^ 1;
                        q.push(v);
                    } else if (color[v] == color[u]) {
                        // Found same color on both sides
                        return false;
                    }
                }
            }
        }
    }

    return true;
}

int main() {
    int T;
    cin >> T;

    for (int t = 1; t <= T; ++t) {
        int M;
        cin >> M;

        vector<pair<string, string>> pairs(M);
        for (int i = 0; i < M; ++i) {
            cin >> pairs[i].first >> pairs[i].second;
        }

        bool result = isBipartite(pairs);
        cout << "Case #" << t << ": " << (result ? "Yes" : "No") << endl;
    }

    return 0;
}

#### Explanation
1. **輸入處理**：
* 使用 `cin` 讀取輸入。第一個整數 **T** 表示測資的數量。
* 對於每個測資，讀取仇人對的數量 **M**，然後讀取 **M** 對成員的名字。
2. **構建圖**：
* 使用 `unordered_map` 構建圖，其中每個鍵是成員，值是一個包含與之有衝突的成員的列表。
3. **使用 BFS 檢查二分圖**：
* 對每個未著色的節點進行 BFS。
* 節點用兩種顏色 (用 0 和 1 表示) 著色。
* 如果發現衝突 (即兩個相鄰的節點具有相同的顏色)，函數返回 `false`。
* 如果 BFS 完成而未發現衝突，則該圖是二分圖。
4. **輸出**：
* 對於每個測資輸出指定格式的結果。如果圖是二分圖，輸出 "Yes"，否則輸出 "No"。

### Complexity Analysis
#### Time Complexity
1. **讀取輸入的時間**：
* 讀取測資數量 **T** 的時間是 $O(1)$。
* 對於每個測資：
* 讀取仇人對的數量 **M** 的時間是 $O(1)$。
* 讀取每對成員的時間是 $O(M)$，因為每對成員都需要單獨讀取。
2. **構建圖的時間**：
* 對於每對成員，我們將他們加入圖中，這需要 $O(2M)$ 的時間，因為我們需要將每個成員插入到 `unordered_map` 中並添加到相應的列表中。插入到 `unordered_map` 和向 `vector` 添加元素的操作都是 $O(1)$ 的時間複雜度。
3. **BFS 檢查是否為二分圖的時間**：
* 假設最壞情況下，每個仇人對的成員均不重複，因此 $N \approx 2M$。
* 每個節點只會被訪問一次，並且每條邊也只會被檢查一次。這樣，BFS 的時間複雜度為 $O(N + M)$。
* 由於 $N \approx 2M$，我們可以將其簡化為 $O(2M + M) = O(3M) = O(M)$。

因此，對於每個測資，整體時間複雜度為：
$O(M) + O(2M) + O(M) = O(4M) = O(M)$

由於每個測資都是獨立處理的，因此，對於 **T** 個測資，總時間複雜度為：
$O(T) \cdot O(M) = O(T \cdot M)$

#### Space Complexity
1. **圖的存儲**：
* 我們使用 `unordered_map` 來存儲圖，`unordered_map` 的鍵是成員的名字，值是包含相鄰成員的列表。這樣的空間複雜度為 $O(N + M)$。
* 由於 $N \approx 2M$，我們可以將其簡化為 $O(2M + M) = O(3M) = O(M)$。
2. **顏色標記的存儲**：
* 我們使用 `unordered_map` 來存儲每個節點的顏色，這需要 $O(N)$ 的空間。
* 由於 $N \approx 2M$，這可以簡化為 $O(2M) = O(M)$。
3. **BFS 隊列**：
* 在最壞情況下，隊列中會包含所有節點，因此需要 $O(N)$ 的空間。
* 由於 $N \approx 2M$，這可以簡化為 $O(2M) = O(M)$。

因此，總空間複雜度為：
$O(M) + O(M) + O(M) = O(3M) = O(M)$

#### Summary
* **時間複雜度**：$O(T \cdot M)$
* **空間複雜度**：$O(M)$
:::

## Notes
1. 題目的背景設定來源於 2008 年的一部音樂迷你劇《糟糕博士的歡唱部落格》(Dr. Horrible's Sing-Along Blog)，此音樂劇在當時獲得了很大的反響，也榮獲了多項獎項，如最佳網絡劇觀眾選擇獎、最佳喜劇網絡劇導演獎、最佳喜劇網絡劇編劇獎、最佳喜劇網絡劇男演員 (哈里斯) 獎、最佳剪輯、最佳攝影和最佳原創音樂獎。

## References
1. https://github.com/google/coding-competitions-archive/blob/main/kickstart/2013/practice_round/bad_horse/statement.pdf
2. https://en.wikipedia.org/wiki/Dr._Horrible%27s_Sing-Along_Blog