Code Submission Evaluation System Login

HIIT Open 2018

Start:2018-05-26 11:00:00
End:2018-05-26 16:00:00

Tasks | Messages | Scoreboard | Statistics

CSES - HIIT Open 2018 - Data Packet RoutingCSES - Data Packet Routing

Data Packet Routing

Time limit:1.00 s
Memory limit:512 MB

You have $n$ computers, numbered $1, 2, \dotsc, n$, and you need to find the best way to route data packets in a computer network.

There are $m$ routing requests. Each routing request is of the form $(x,y)$, which indicates that you will need to transmit 1 data packet from computer $x$ to computer $y$. We say that $x$ is the source and $y$ is the destination of this data packet.

You know that each computer is the source of at most $n$ data packets, and each computer is the destination of at most $n$ data packets.

There are bidirectional communication links between all pairs of computers. In one round, you can send at most one data packet from $x$ to $y$ and at most one data packet from $y$ to $x$, for each pair of computers $(x,y)$.

Note that you do not need to send data packets directly to their final destinations. You can also keep any number of data packets waiting at any computer. Hence to process a routing request $(10,20)$ in a network with $n = 30$ computers, one solution might be to send the packet first from $10$ to $30$, then let it wait for one round at $30$, and finally send it from $30$ to $20$. The only restriction is that in each round each communication link carries at most one packet per direction.

Your task is to minimize the number of rounds needed to transmit all data packets to their final destinations.


The first input line has one integer $t$: the number of test cases.

Each test case begins with a line that contains two integers $n$ and $m$: the number of computers and routing requests. After this, there are $m$ lines. Each line represents one routing request: it contains two integers $x$ and $y$ which indicate that there is one packet with source $x$ and target $y$.


For each test case, print one line: the smallest number of rounds in which you can route all requests to their final destinations.


10 3
1 2
2 1
3 4
10 3
1 2
1 2
3 4