Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- void dbg_out() { cerr << endl; }
- template<typename Head, typename... Tail>
- void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
- #define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
- #define rng_init mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
- #define all(x) (x).begin(), (x).end()
- #define sz(x) (int) (x).size()
- // #define int long long
- const int MXN = 5e5 + 5, INF = 1e9 + 5;
- pair<int, int> parent[MXN];
- int bipartite[MXN], compSz[MXN];
- void make_set(int v) {
- parent[v] = make_pair(v, 0);
- compSz[v] = 0;
- bipartite[v] = true;
- }
- pair<int, int> find_set(int v) {
- if (v != parent[v].first) {
- int parity = parent[v].second;
- parent[v] = find_set(parent[v].first);
- parent[v].second ^= parity;
- }
- return parent[v];
- }
- void add_edge(int a, int b) {
- pair<int, int> pa = find_set(a);
- a = pa.first;
- int x = pa.second;
- pair<int, int> pb = find_set(b);
- b = pb.first;
- int y = pb.second;
- if (a == b) {
- if (x == y)
- bipartite[a] = false;
- } else {
- if (compSz[a] < compSz[b])
- swap (a, b);
- parent[b] = make_pair(a, x^y^1);
- bipartite[a] &= bipartite[b];
- if (compSz[a] == compSz[b])
- ++compSz[a];
- }
- }
- bool is_bipartite(int v) {
- return bipartite[find_set(v).first];
- }
- void solve() {
- int N, M, Q;
- cin >> N >> M >> Q;
- for (int i = 0; i < N; i++)
- make_set(i);
- for (int i = 0; i < M; i++) {
- int u, v;
- cin >> u >> v;
- add_edge(u, v);
- }
- for (int i = 0; i < N; i++) {
- find_set(i);
- // dbg(i, parent[i].first, parent[i].second);
- }
- while (Q--) {
- int u, v;
- cin >> u >> v;
- if (parent[u].first != parent[v].first) {
- cout << "none\n";
- } else if (!is_bipartite(u)) {
- cout << "both\n";
- } else {
- // dbg(u, v, parent[u].second, parent[v].second, parent[u].first);
- int val = parent[u].second ^ parent[v].second;
- if (val & 1) cout << "odd\n";
- else cout << "even\n";
- }
- }
- }
- signed main() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- #ifdef local
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- int TC = 1;
- // cin >> TC;
- while (TC--) solve();
- }
Add Comment
Please, Sign In to add comment