APCS-202111-4. 真假子圖

zerojudge網址 https://zerojudge.tw/ShowProblem?problemid=g598

情報調查局內有 n 個工作人員, 調查局負責人將這些人秘密分成兩組 A 和 B 並不讓其他人知道, 並將合作名單分配給組長, 合作名單是由很多個 pair 組成, 每個 pair (x,y) 代表 x 和 y 需要合作完成任務, 並且保證 x 和 y 不會同時在 A 組或是同時在 B 組 組長不小心將這個合作名單分配遺失, 僅剩下其中 m 個 pair, 為了要復原這些失去的資料, 組長派出了另外 p 個調查員編號 1 到 p 去調查這個合作關係, 每一個調查員都會回傳恰好 k 個 pair 的資料回來 有些調查員回傳的資料和組長手上的資料會產生矛盾 (意即加上這 k 個 pair 和組長手上存留的 m 個 pair 會使得這些人是被分成 A, B 兩組這件事產生矛盾),請將回傳錯誤結果的調查員編號由小到大輸出出來, 保證至少一個且最多三個。

另外保證若調查員的 k 個 pair 的結果和組長存留的 m 個 pair 不會產生矛盾, 則保證調查員的資料一定和原本 A, B 分組吻合

輸入說明

第一行先輸出兩個正整數 n 和 m 第二行來有 2m 個非負整數兩兩形成一個數對，表示目前還留存的 m 個 pair 第三行有兩個正整數 p 和 k 並且接下來的 p 行每行有 2k 個非負整數, 兩兩形成一對代表某個調查員找到的 k 個 pair

輸出說明

由小到大輸出會形成矛盾的調查員編號，每個編號各自獨立一行

輸入範例1

7 5

0 1 0 2 1 3 2 3 4 5

2 3

0 6 2 4 3 6

0 6 0 3 3 5

輸出範例1

2

輸入範例2

5 2

0 3 2 3

3 2

0 2 2 4

0 1 1 2

3 4 2 4

輸出範例2

1

3

解題策略

(1)DFS、並查集、二分圖(本程式)

(2)二分搜尋，如果由上到下第一個觀察員i有錯，則第1個到第i-1個觀察員都是正確的，使用二分搜尋逼近出第i個觀察員為錯的，去除第i個，找出第i個以後觀察員是否有錯，如果有繼續去除，直到找到三個為止，或都沒有錯。

這題有許多技巧，每一個點都需要上色，就算組長沒有提到的節點也需要上色，

並查集是針對上色(群組編號)不是個別節點，參考https://hackmd.io/@peienwu/APCS1107