P5870 [SEERC 2018] Modern Djinn

You are not a leader; you are a president. Luckily, you have a djinn that can grant your wishes. One of your wishes is to pretend that your society has democracy. The society is simple. There are $N$ people in the society, numbered from $1$ to $N$. Some people are “happy”, while others are ordinary (“unhappy”). Humans are very strange: people feel happy only when others are unhappy. There are $M$ wishes in total, numbered from $1$ to $M$. $X \rightarrow Y$ means that $X$ wants $Y$ to be unhappy. A person $X$ is happy if and only if at least one of their wishes is fulfilled. Democracy is not that complicated either. Some say that to achieve democracy, you need at least half of the people to be happy (or half of the wishes to be fulfilled), but that is not entirely true. As I said, you are a good president, not a good leader. You can define democracy through the media. Therefore, among all $M$ wishes, you decide to fulfill at least $\lfloor M/4 \rfloor + 1$ wishes. The remaining task is to choose which wishes you want to fulfill, and then the djinn will take care of everything.

The input contains multiple test cases. The first line contains an integer $T$, the number of test cases. The following lines give the test cases in order. For each test case, the first line contains two positive integers $N$ and $M$, representing the number of people in the society and the number of wishes. The next $M$ lines each contain two integers $X, Y$, describing a wish: $X$ wants $Y$ to be unhappy.

For each test case, output an integer $K$ on the first line, the number of wishes to be fulfilled. Output $K$ integers on the second line, the indices of the fulfilled wishes. The order does not matter.

**Constraints** - $1 \leq T \leq 10,000$ - $2 \leq N \leq 100,000$ - $1 \leq M \leq 200,000$ - There is no wish where $X$ wants $X$ to be unhappy. - There may be multiple identical wishes where $X$ wants $Y$ to be unhappy. - For each test case, a solution is guaranteed to exist. - Any correct solution is accepted. **Sample Explanation** In the first test case, we can fulfill at most $1$ wish; outputting any wish is valid. In the second test case, another valid solution is to fulfill wishes $1$, $3$, and $4$. At least $2$ wishes must be fulfilled. Translated by ChatGPT 5