27645번 - Internet problem (Hard) 다국어

Lisa and Sarah have exposed a massive conspiracy and now they’re on the run from the corrupt government. Being together makes it too risky that they could both be captured, so they have to communicate through the Internet. But the normal Internet isn’t safe enough, so they send each other secret messages through the dark web.

On the dark web, every message can take a long and convoluted path through many servers until it reaches its destination, and it might even go through one server multiple times. This makes messages much harder to trace.

But Lisa is still worried. What if the government has already hacked one of the servers of the dark web? If the hacked server is in a good central location, it could intercept all of her messages to Sarah, regardless of what 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 network links. Links are directed – if one server can transmit a message to another, the opposite doesn’t have to be true. Lisa is connected to server 1 and Sarah is connected to server n. Whenever Lisa wants to send a message to Sarah, she chooses a route for the message: a sequence of consecutive network links that goes 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 about their plans, and “at most once” is needed so their hard drives don’t fill up with duplicates.)

Find all the servers which satisfy that condition.

The first line of the input file contains an integer t specifying 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, b (1 ≤ a, b ≤ 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 will be 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 a space-separated list of numbers of those servers, in the order in which messages from Lisa to Sarah go through them.

Note that for some test cases there may be no path from Lisa to Sarah. If that is the case, output an empty set of servers.

• 2 ≤ n ≤ 500 000
• 0 ≤ m ≤ 1 000 000

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

Second test case: The government doesn’t want to get any duplicates, so they can’t hack either server. Lisa and Sarah are safe.

Third test case: Lisa can’t send any messages anyway, so there is nothing to hack.

Fourth test case: The government can’t hack both 2 and 3 at once. If they hack only 2, or only 3, they won’t see all messages.