#include <bits/stdc++.h>
using namespace std;
#define pii pair<ll,ll>
#define REP(i,x,y) for(ll i=x;i<=y;i++)
#define freeopen freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
#define mod 1000000000
#define pb push_back
#define mk make_pair
#define ll long long
#define foor(x,vec) for(auto x:vec ){cout<<x<<" ";}
#define fi first
#define se second
#define MAXN 500069
#define lld long double
#define cha ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ffl fflush(stdout)
#define sst string
#define pii pair<ll,ll>
ll mvx[]={0,0,-1,1};
ll mvy[]={1,-1,0,0};
int deg[MAXN];
void initialize(int n){
REP(i,1,n)deg[i]=n-1;
}
bool hasEdge(int u, int v){
if(deg[u]==1 || deg[v]==1){
deg[u]=0;
deg[v]=0;
return 1;
}
else{
deg[u]--;
deg[v]--;
return 0;
}
}
