P10940 Dancing Night

Company $L$ and company $H$ held a social party. At the party, $N$ employees from company $L$ and $M$ employees from company $H$ plan to have a ballroom dance. Among these people, some employees from company $L$ and some employees from company $H$ know each other. There are $T$ such acquaintance pairs. At the dance, each employee will try to choose one employee from the other company that they know as a partner, and each employee can dance at most once. The more dances are completed, the more lively the party becomes. To keep the party lively, they want to know which acquaintance pairs of employees, if they dance together, will reduce the maximum number of dances that the whole party can complete.

The first line contains three integers $N, M, T$. The next $T$ lines each contain two integers $x, y$, meaning employee $x$ of company $L$ and employee $y$ of company $H$ know each other.

The first line contains an integer $cnt$, which is the number of acquaintance pairs such that, if that pair dances, the maximum number of dances the whole party can complete will decrease. The second line contains $cnt$ integers, output in increasing order, which are the indices of such acquaintance pairs (i.e., the position of that acquaintance pair in the input). If $cnt=0$, output an empty line.

Constraints: $1 \le N, M \le 10000$, $1 \le T \le 100000$, $1 \le x \le N$, $1 \le y \le M$. Translated by ChatGPT 5