1548A - Web of Lies - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define vll vector<ll>
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define no cout<<"NO"<<endl
#define yes cout<<"YES"<<endl
#define min3(a,b,c) min(a,min(b,c))
#define min4(a,b,c,d) min(a,min(b,min(c,d)))
#define max3(a,b,c) max(a,max(b,c))
#define max4(a,b,c,d) max(a,max(b,max(c,d)))
#define slow ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)

#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
#else
#define debug(x)
#endif

void _print(ll t) {cerr << t;}
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(double t) {cerr << t;}

template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
 
const ll N=2e5+1;
const ll mod=1e9+7;



void solve()
{
   ll n,k;
   cin>>n>>k;
   map<ll,set<ll>> m;

   for(int i=1;i<=k;i++){
      ll x,y;
      cin>>x>>y;
      m[x].insert(y);
      m[y].insert(x);
   }

   ll cnt=m[1].size()?1:0;
    for(int i=2;i<=n;i++){
       if(m[i].upper_bound(i-1)!=m[i].end()){
        
        cnt++;
        
       }
    }

   ll q;
   cin>>q;
   while(q--){
    ll x;
    cin>>x;
    if(x==1){
      ll a,b;
      cin>>a>>b;
      bool f1=false,f2=false;

      if(m[a].lower_bound(a)!=m[a].end()) f1=true;
      if(m[b].lower_bound(b)!=m[b].end()) f2=true;
      m[a].insert(b);
      m[b].insert(a);
      if(!f1){
        if(m[a].lower_bound(a)!=m[a].end()) cnt++;
      }
      if(!f2){
        if(m[b].lower_bound(b)!=m[b].end()) cnt++;
      }
    }
    else if(x==2){
      ll a,b;
      cin>>a>>b;
       bool f1=false,f2=false;

    
     m[a].erase(b);
     m[b].erase(a);
     
     if(b>a) swap(a,b);

      if(m[b].lower_bound(b)==m[b].end()) cnt--;
     

    }
  else{
 
    cout<<n-cnt<<endl;
   }
  }
}

int main() {

#ifndef ONLINE_JUDGE
  freopen("Error.txt", "w", stderr);
#endif


  slow;

  ll t = 1;
  // ll ks = 1;
 // cin >> t;
  while (t--)
  {
    // cout << "Case #" << ks++ << ":" << ' ';
    solve();
  }

  return 0;
}