時間限制 4000 ms ・ 記憶體限制 512 MB
題目描述
n 位工作人員被分為 A、B 兩組。每個合作數對要求兩人分屬不同組。現有 m 對已知的正確合作關係，另外 p 位調查員各提出 k 對關係。 逐一判斷每位調查員：只把該人的 k 對加入原有 m 對，若已不可能將所有人分成兩組且每一對都跨組，該人的資料就有矛盾。保證有 1 至 3 位調查員矛盾；無矛盾的資料也保證符合原本的實際分組。
輸入格式
第一行為 n、m，1 ≤ n,m ≤ 20000，人員編號為 0 至 n−1。第二行有 2m 個非負整數，每兩個構成一對。第三行為 p、k，2 ≤ p ≤ 10000，1 ≤ k ≤ 20。接著 p 行，每行 2k 個整數為該調查員的 k 對關係。每個人被數對提及的次數不超過 150。
輸出格式
將有矛盾的調查員編號由小到大輸出，一行一個；調查員編號為 1 至 p。
範例測資
範例輸入 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
請先登入後再提交程式碼
討論與題解
載入討論區…