#include #include #include #include #include #include #include #pragma GCC target ("avx") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #define rep(i,n) for (ll i = 0;i < (ll)(n);i++) #define Yes cout << "Yes" << "\n"// YESの短縮 #define No cout << "No" << "\n"// NOの短縮 #define rtr0 return(0)//return(0)の短縮 #define gyakugen(x) modpow(x,mod - 2,mod); #define agyakugen(x) modpow(x,amod - 2,amod); using namespace std; using ll = long long;//63bit型整数型 using ld = long double;//doubleよりも長い値を保存できるもの using ull = unsigned long long;//符号がない64bit型整数 ll mod = 998244353; ll amod = 1000000007; ll MINF = -5000000000000000000; ll INF = 5000000000000000000; ll BAD = -1; vectortate = {0,-1,0,1};//グリッド上の全探索時の四方向の上下のチェック vectoryoko = {1,0,-1,0};//グリッド上の全探索時の四方向の右左のチェック vectoreightx = {0,-1,-1,-1,0,1,1,1};//グリッド上の全探索時の八方向の上下のチェック vectoreighty = {1,1,0,-1,-1,-1,0,1};//グリッド上の全探索時の八方向の右左のチェック vectorhexsax = {0,1,1,0,-1,-1}; vectorhexsay = {1,1,0,-1,-1,0}; //返り値は素数のリスト。 void nextbit(vector&bit,ll N,ll x){//bitと配列の長さN,x進数 bit[0]++; for(ll i = 0;i isprime; vector < ll > Era(int n){//書き方 vector[] = Era(x); とやるとxまでの素数が出てくる。 isprime.resize(n, true); vector < ll > res; isprime[0] = false; isprime[1] = false; for(ll i = 2; i < n; ++i) isprime[i] = true; for(ll i = 2; i < n; ++i) { if(isprime[i]) { res.push_back(i); for(ll j = i * 2; j < n; j += i) isprime[j] = false; } } return res; } //      素数判定 21~35 long long modpow(long long a, long long n, long long mod) { long long res = 1; while (n > 0) { if (n & 1) res = res * a % mod; a = a * a % mod; n >>= 1; } return res; } // モッドを使った累乗 template struct dijkstra{ public: vector>>graph; vectorans; priority_queue,vector>,greater>>pq; void do_dijkstra(T start){//頂点xからダイクストラを行う pq.push({0,start}); ans[start] = 0; while(true){ if(pq.empty())break; T cost = pq.top().first; T vertex = pq.top().second; pq.pop(); for(T i = 0;i nextcost){ ans[nextvertex] = nextcost; pq.push({nextcost,nextvertex}); } } } } void make_indirectedgraph(T u,T v,T cost){//無向辺のグラフ作成 graph[u].push_back({v,cost}); graph[v].push_back({u,cost}); } void make_directedgraph(T u,T v,T cost){//有向辺のグラフ作成 graph[u].push_back({v,cost}); } T output(T end){//答えを出す return ans[end]; } void reset(T N){//リセット graph.clear(); ans.clear(); for(ll i = 0;i>(0)}); ans.push_back(INF); } } }; template struct unionfind{//主に、マージ、確認、親が同じかどうかの判定、親の確認 public: vectorparent; vector>child; void check(T N){//親の確認、バグ取りに有効 for(T i = 0;i child[b].size()){ while(true){ if(child[b].empty())break; child[a].insert(*child[b].begin()); parent[*child[b].begin()] = a; child[b].erase(*child[b].begin()); } } else{ while(true){ if(child[a].empty())break; child[b].insert(*child[a].begin()); parent[*child[a].begin()] = b; child[a].erase(*child[a].begin()); } } } } bool same(T x,T y){//親が同じかどうかの判定 T a = leader(x); T b = leader(y); if(a == b)return true; else return false; } void reset(T N){//始めるときの初期化 parent.clear(); child.clear(); parent.resize(N); child.resize(N); for(T i = 0;i> N >> M; vector>>graph(N,vector>(0)); for(ll i = 0;i> a >> b; a--; b--; graph[a].push_back({b,i}); } if(M%2 == 1){ cout << -1 << "\n"; rtr0; } vectorvisited(M); vectorcolor(M); ll rcount = 0; ll bcount = 0; for(ll i = 0;i M/2){ cout << -1 << "\n"; rtr0; } for(ll i = 0;i M/2){ cout << -1 << "\n"; rtr0; } for(ll i = 0;i