True and False Subgraphs (APCS 2021-11 Expert)

Each of \(n\) people belongs to one of two factions. There are \(m\) known relations, each requiring its endpoints to be in different factions; these relations are consistent. Each of \(p\) investigators reports \(k\) additional opposite-faction pairs. For each investigator independently, combine only that report with the known relations and determine whether a two-faction assignment exists. Output the investigators whose reports are impossible.

Input Format

The first line contains \(n,m\). The second contains \(2m\) integers, with each consecutive pair describing a known relation. The third line contains \(p,k\). The next \(p\) lines each contain \(2k\) integers describing one report. People are numbered \(0\) through \(n-1\), and investigators \(1\) through \(p\).

Output Format

Print every invalid investigator index in increasing order, one per line.

Constraints

\(1\le n,m\le20000\), \(2\le p\le10000\), \(1\le k\le20\). A person appears at most \(150\) times over all known and reported pairs. There are between \(1\) and \(3\) invalid investigators. All valid reports together with the known relations are consistent with a single two-faction assignment.

Scoring

• 20 points: \(n,m\le100\), \(p\le20\), exactly one invalid investigator.
• 20 points: \(n,m\le5000\), \(p\le200\).
• 60 points: No additional restrictions.

Each scored test is worth 5 points.

Sample Input 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

Sample Output 1

2

Sample Input 2

5 2
0 3 2 3
3 2
0 2 2 4
0 1 1 2
3 4 2 4

Sample Output 2

1
3

Source

APCS 2021-11 public archive version: g598。