真假子圖 (APCS 2021-11 高級)

有 \(n\) 位人物，每人屬於兩個陣營之一。已知的 \(m\) 對關係都表示兩端人物分屬不同陣營，且已知關係彼此相容。有 \(p\) 位調查員，各自提出 \(k\) 對「不同陣營」關係。對每位調查員，僅將他的關係與原本已知關係合併，判斷能否將所有人物分成兩個陣營。輸出所有不可能成立的調查員編號。不同調查員必須獨立驗證。

輸入格式

第一行為 \(n,m\)。第二行含 \(2m\) 個整數，每相鄰兩個為一對已知關係。第三行為 \(p,k\)。接下來 \(p\) 行，每行含 \(2k\) 個整數，給出該調查員提出的 \(k\) 對關係。人物編號為 \(0\) 到 \(n-1\)，調查員編號為 \(1\) 到 \(p\)。

輸出格式

依編號遞增，每行輸出一位不合法的調查員編號。

資料範圍

\(1\le n,m\le20000\)，\(2\le p\le10000\)，\(1\le k\le20\)。每個人物編號在全部已知與調查關係中總共出現至多 \(150\) 次。不合法調查員有 \(1\) 到 \(3\) 位。所有合法調查員的關係可以與已知關係共同符合某個二分陣營配置。

評分說明

• 20 分：\(n,m\le100\)，\(p\le20\)，恰有一位不合法調查員.
• 20 分：\(n,m\le5000\)，\(p\le200\).
• 60 分：無額外限制.

每筆計分測資各為 5 分。

範例輸入 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

題目來源

APCS 2021 年 11 月實作題第 4 題。

題敘參考 ZeroJudge g598「真假子圖」 整理，細節可能與正式試題有出入。