题解

代码

#include <set>
#include <cstdio>
#include <utility>
#include <algorithm>
using namespace std;

#define rep( i, a, b ) for( int i = (a) ; i <= (b) ; i ++ )
#define per( i, a, b ) for( int i = (a) ; i >= (b) ; i -- )

typedef pair<int, int> Node;

const int INF = 0x3f3f3f3f;
const int MAXN = 1e5 + 5, MAXM = 2e5 + 5;

#define DX first
#define DY second

template<typename _T>
void read( _T &x )
{
	x = 0; char s = getchar(); int f = 1;
	while( s < '0' || '9' < s ) { f = 1; if( s == '-' ) f = -1; s = getchar(); }
	while( '0' <= s && s <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar(); }
	x *= f;
}

template<typename _T>
void write( _T x )
{
	if( x < 0 ) putchar( '-' ), x = - x;
	if( 9 < x ) write( x / 10 );
	putchar( x % 10 + '0' );
}

struct Edge
{
	int to, nxt;
}Graph[MAXM << 2];

set<Node> s;
Node seq[MAXN];

int dist[MAXN << 1];

int head[MAXN << 1];
int N, M, cnt;

bool Cmp( const Node &x, const Node &y )
{
	int tx = x.DX + x.DY, ty = y.DX + y.DY;
	return tx == ty ? x.DX < y.DX : tx < ty;
}

void Clean()
{
	cnt = 0, s.clear();
	rep( i, 1, N << 1 ) head[i] = 0;
}

void AddEdge( const int from, const int to )
{
	Graph[++ cnt].to = to, Graph[cnt].nxt = head[from];
	head[from] = cnt;
}

void AddE( const int from, const int to )
{
	AddEdge( from, to ), AddEdge( to, from );
}

void BFS()
{
	static int q[MAXN << 1], h, t;
	h = 1, t = 0; rep( i, 1, N << 1 ) q[i] = 0;
	rep( i, 1, N << 1 ) dist[i] = INF;
	dist[q[++ t] = 1] = 0;
	for( int u, v ; h <= t ; )
	{
		u = q[h ++];
		for( int i = head[u] ; i ; i = Graph[i].nxt )
			if( dist[v = Graph[i].to] > dist[u] + 1 )
				dist[q[++ t] = v] = dist[u] + 1;
	}
}

int main()
{
	int T;
	read( T );
	while( T -- )
	{
		read( N ), read( M ), Clean();
		rep( i, 1, M ) { int a, b; 
			read( a ), read( b ); 
			AddE( a, b + N ), AddE( a + N, b );
		}
		BFS(); bool flg = true;
		rep( i, 1, N )
		{
			if( dist[i] < dist[i + N] ) seq[i] = Node( dist[i], dist[i + N] );
			else seq[i] = Node( dist[i + N], dist[i] );
			if( seq[i].DY == INF ) flg = false;
		}
		if( flg == false ) { write( N - 1 ), putchar( '\n' ); continue; }
		
		sort( seq + 1, seq + 1 + N, Cmp ); int ans = 0, t = 0;
		for( int i = 1, r ; i <= N ; i = r )
		{
			for( r = i ; r <= N && seq[r] == seq[i] ; r ++ );
			s.insert( seq[i] );
			Node lu = Node( seq[i].DX - 1, seq[i].DY - 1 );
			flg = s.find( lu ) != s.end();
			if( t <= r - i ) 
			{
				if( flg ) ans += ( i > 1 ) * ( r - i );
				else ans += ( i > 1 ) * ( r - i ), t = r - i;
			}
			else ans += ( i > 1 ) * t, t = r - i;
			if( r > N || seq[r] != Node( seq[i].DX + 1, seq[i].DY - 1 ) )
			{
				if( seq[i].DX + 1 != seq[i].DY ) ans += t;
				else ans += t + 1 >> 1; t = 0;
			}
		}
		write( ans ), putchar( '\n' );
	}
	return 0;
}
```cpp