#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #pragma warning(disable:4996) //#define ATCODER #ifdef ATCODER #include #endif typedef long long ll; typedef unsigned long long ull; #define LINF 9223300000000000000 #define LINF2 1223300000000000000 #define LINF3 1000000000000 #define INF 2140000000 const long long MOD = 1000000007; //const long long MOD = 998244353; using namespace std; #ifdef ATCODER using namespace atcoder; #endif vector bfs(int s, const vector>& G, vector* ppr) { // G[from]={to} の形のグラフ。pprは最短距離のときのprevを記録 queue que; vector d(G.size(), INF); if(ppr) ppr->resize(G.size(), -1); d[s] = 0; que.push(s); while (!que.empty()) { int curr = que.front(); que.pop(); int i; for (i = 0; i < (int)G[curr].size(); i++) { int next = G[curr][i]; if (d[curr] + 1 < d[next]) { d[next] = d[curr] + 1; if(ppr) (*ppr)[next] = curr; que.push(next); } } } return d; } void solve() { int n, m; scanf("%d%d", &n, &m); vector> g(n*2); // g[from]={to} の形のグラフ。ただし頂点を倍加(始点からの移動距離が偶数/奇数を区別) vector> f(n); // f[to]={from} の形のグラフ。 vector a(m), b(m); map, int> ed; // (from,to)->edgeid int i, j; for (i = 0; i < m; i++) { scanf("%d%d", &a[i], &b[i]); a[i]--; b[i]--; ed[make_pair(a[i], b[i])] = i; f[b[i]].push_back(a[i]); g[a[i]*2].push_back(b[i]*2+1); g[a[i]*2+1].push_back(b[i]*2); } vector ans; // 長さnの0,1からなる配列。0,1それぞれR,Gを表す for (i = 0; i < n; i++) { vector pr; vector dist = bfs(2 * i, g, &pr); for (j = 0; j < n; j++) { if (dist[j * 2] == INF && dist[j * 2 + 1] == INF) { printf("-1"); return; } } if (ans.empty() && f[i].size() > 1 && dist[i * 2 + 1] < INF) { // 奇数閉路で、かつ i に他からも有向辺が来ている vector ans0(m); // 長さnの0,1からなる配列。0,1それぞれR,Gを表す vector flag(n); // loopに使われたnodeに印をつける int curr = i * 2 + 1; int bad = 0; int tmp = 1; int dd = 0; while ( 1 ) { if (flag[curr/2]) { bad = 1; break; // 同じnodeを2回通るループは除外 } else { flag[curr / 2] = 1; dd++; } int prev = pr[curr]; int edge = ed[make_pair(prev / 2, curr / 2)]; ans0[edge] = tmp; if (dd==2) { ans0[edge] = 1 - ans0[edge]; } tmp = 1 - tmp; curr = prev; if (curr == i * 2) { ans0[edge] = 1 - ans0[edge]; break; } } if (bad == 0) { ans.swap(ans0); } } } if (ans.empty()) { printf("-1"); return; } for(i=0;i