Indiana Jones Among Zombies 2

In the earlier problem "Indiana Jones Among Zombies", the Amulet of Body and Mind Control that Indiana found turned out to be broken. But how would the story have gone if the amulet had actually worked?

The labyrinth has the same structure as before.

• The labyrinth has $N$ rooms numbered from $1$ to $N$. Indiana is in room $1$. Each of the other rooms initially holds one undead (a zombie). Rooms are joined by two-way corridors.
• Every turn, each living zombie moves one step along a corridor to the next room on a shortest path from its current room to Indiana's room. If it cannot reach Indiana's room, it stays where it is. If several shortest paths leave a room, the zombies there take the corridor that appears first in the input.

This time Indiana carries a working amulet, which he wants to use to make the undead fight one another (over the right to eat him). With the amulet, right at the start Indiana may choose any number of disjoint pairs of undead and declare each pair to be rivals.

The moment one zombie of a rival pair stands in the room that the other zombie of the same pair is about to move into on the next turn (that is, the other is exactly one step behind), a fight breaks out at once (right then, not on the next turn). The zombie that is farther from Indiana realizes its rival is ahead in the race to eat Indiana and hurls itself at its opponent through the corridor between them. Their heads collide and both die.

A zombie that reaches Indiana's room is killed instantly by a blow of the amulet, and from that moment it can no longer fight its rival.

Find the maximum number of disjoint rival pairs Indiana can choose so that every chosen pair actually ends up fighting as described.

The first line contains a natural number $Z$ ($Z = 1$), the number of test sets. The test sets follow on the next lines.

The first line of each test set contains two space-separated natural numbers $N$ and $M$ ($1 \le N, M \le 10^6$): $N$ is the number of rooms in the labyrinth and $M$ is the number of corridors.

Each of the next $M$ lines describes one corridor as a pair of distinct natural numbers $A$ and $B$ ($1 \le A, B \le N$), meaning there is a two-way corridor joining rooms $A$ and $B$. Every pair of rooms is joined by at most one corridor.

For each test set, print on its own line the maximum number of rival zombie pairs that can be provoked into a fight.