Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- typedef pair<int, int> pi;
- typedef pair<ll,ll> pl;
- typedef vector<int> vi;
- typedef vector<ll> vl;
- #define FOR(i, a, b) for (int i=a; i<(b); i++)
- #define F0R(i, a) for (int i=0; i<(a); i++)
- #define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
- #define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
- #define trav(a,x) for (auto& a : x)
- #define sz(x) (int)(x).size()
- #define pb push_back
- #define f first
- #define s second
- #define lb lower_bound
- #define ub upper_bound
- #define all(x) x.begin(), x.end()
- #define ins insert
- void solve() {
- int N, M; cin >> N >> M;
- vector<int> graph[2*N];
- F0R(i, M) {
- int X, Y; cin >> X >> Y; X--; Y--;
- graph[X].pb(Y+N);
- graph[X+N].pb(Y);
- graph[Y].pb(X+N);
- graph[Y+N].pb(X);
- }
- int dist[2*N]; F0R(i, 2*N) dist[i] = 1000000;
- queue<int> q;
- q.push(0);
- dist[0] = 0;
- while (!q.empty()) {
- int x = q.front(); q.pop();
- trav(a, graph[x]) {
- if (dist[a] > dist[x] + 1) {
- dist[a] = dist[x] + 1; q.push(a);
- }
- }
- }
- if (dist[N] > 2*N+10) {
- cout << N-1 << endl; return;
- }
- int ans = 0;
- map<int, int> cnt[4*N+10];
- F0R(i, N) {
- int x = min(dist[i], dist[i+N]); int y = max(dist[i], dist[i+N]);
- cnt[x+y][x]++;
- }
- F0Rd(m, 4*N+10) {
- int lst = -100;
- int cur = 0;
- trav(a, cnt[m]) {
- if (a.s == 0) continue;
- //cout << m << " " << a.f << " " << a.s << endl;
- if (lst < a.f-1) {
- if (lst * 2 + 1 == m) {
- ans += (cur+1)/2;
- } else ans += cur;
- cur = 0;
- }
- lst = a.f;
- if (m >= 2 && cnt[m-2][a.f-1]) {
- ans += max(cur, a.s);
- cur = min(cur, a.s);
- } else {
- ans += max(cur, a.s);
- cur = a.s;
- }
- }
- if (lst*2+1 == m) {
- ans += (cur+1)/2;
- } else ans += cur;
- }
- ans--;
- /*sort(all(ps));
- trav(a, ps) {
- cout << a.f << " " << a.s << endl;
- }
- FOR(i, 1, 2*N+10) {
- for (auto it = cnt[i].rbegin(); it != cnt[i].rend(); it++) {
- int k = it->s;
- int p = it->f;
- k -= min(k, cnt[i-1][p]);
- int x = min(k, cnt[i-1][p-2]);
- cnt[i-1][p-2] -= x;
- k -= x;
- ans += k; if (p == 1) ans -= k/2;
- }
- }
- int on[2*N+10], off[2*N+10]; F0R(i, 2*N+10) on[i] = 0, off[i] = 0;
- int flow[2*N+10]; F0R(i, 2*N+10) flow[i] = 0;
- F0R(i, N) {
- int x = min(dist[i], dist[i+N]); int y = max(dist[i], dist[i+N]);
- on[x]++; if (y < 2*N+10) off[y]++;
- if (y == x+1) {
- off[y]--; flow[y]++;
- cout << i << " flows" << endl;
- }
- cout << y << " "<< y-x << endl;
- }
- bool found = false;
- FOR(i, 1, 2*N+10) {
- if (!found) {
- ans += on[i] + max(off[i] - off[i-1] - flow[i-1], 0) + (flow[i]+1)/2;
- found = true;
- } else {
- int num = off[i-1] + flow[i-1];
- int x = min(num, off[i]);
- int k = off[i] - x;
- num -= x;
- int l = flow[i] - min(num, flow[i]);
- ans += on[i] + k + (l+1)/2;
- }
- //cout << i << ": " << on[i] << " " << off[i] << " " << flow[i] << " " << ans << endl;
- }*/
- cout << ans << endl;
- }
- int main() {
- ios_base::sync_with_stdio(0); cin.tie(0);
- int T; cin >> T;
- while(T--) {
- solve();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement