Internet problem (Hard)

Lisa and Sarah have exposed a massive conspiracy and are now on the run from a corrupt government. Being together is too risky because both could be captured, so they communicate over the Internet. The normal Internet is not safe enough, so they send each other secret messages through the dark web.

On the dark web, a message can take a long and convoluted path through many servers before it reaches its destination. The path may even pass through one server multiple times, which makes messages harder to trace.

Lisa is still worried. What if the government has already hacked one of the dark web servers? If the hacked server is in a good central location, it could intercept all of her messages to Sarah, regardless of the path they take.

Help Lisa solve her Internet problem!

The dark web consists of $n$ servers, numbered from 1 to $n$. The servers are connected by $m$ directed network links. If one server can transmit a message to another, the opposite does not have to be true. Lisa is connected to server 1 and Sarah is connected to server $n$. Whenever Lisa sends a message to Sarah, she chooses a route: a sequence of consecutive network links from server 1 to server $n$. The route may go through each server multiple times.

The government wants to intercept Lisa's messages to Sarah. They can hack one server so it records all messages that go through it. They want to see every message from Lisa to Sarah exactly once. At least once is needed so they learn all of the plans, and at most once is needed so their hard drives do not fill up with duplicates.

Find all the servers that satisfy this condition.

The first line of the input contains an integer $t$, the number of test cases. Each test case is preceded by a blank line.

The first line of each test case contains the integers $n$ and $m$. Each of the next $m$ lines contains two integers $a$ and $b$ ($1 \le a, b \le n$), meaning that server $a$ can transmit messages directly to server $b$. It may be the case that $a = b$. Each distinct ordered pair $a, b$ is given at most once.

For each test case, output two lines. On the first line, print the number of servers that could be hacked by the government. On the second line, print the numbers of those servers, separated by spaces, in the order in which Lisa's messages pass through them.

If there is no path from Lisa to Sarah, output an empty set of servers.

$2 \le n \le 500000$

$0 \le m \le 1000000$

First test case: All messages must take the same path, so the government could hack any server on that path.

Second test case: The government does not want any duplicates, so they cannot hack either server. Lisa and Sarah are safe.

Third test case: Lisa cannot send any messages at all, so there is nothing to hack.

Fourth test case: The government cannot hack both 2 and 3 at once. If they hack only 2 or only 3, they will not see all messages.