Submission #64086347

---

Source Code Expand

#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;

vector<vector<int>> adj;
vector<int> color;

bool dfs(int u, int c) {
    color[u] = c;
    for (int v : adj[u]) {
        if (color[v] == -1) {
            if (!dfs(v, 1 - c)) return false;
        } else if (color[v] == c) {
            return false;
        }
    }
    return true;
}

int main() {
    int n;
    cin >> n;
    adj.resize(n + 1);
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    color.assign(n + 1, -1);
    dfs(1, 0);

    int a = 0, b = 0;
    for (int i = 1; i <= n; ++i) {
        if (color[i] == 0) a++;
        else b++;
    }

    int cnt = a * b - (n - 1);
    if (cnt % 2 == 1) {
        cout << "First" << endl;
    } else {
        cout << "Second" << endl;
    }
    cout << flush;

    while (true) {
        int i, j;
        for (i = 1; i <= n; ++i) {
            for (j = i + 1; j <= n; ++j) {
                if (color[i] != color[j]) {
                    bool has_edge = false;
                    for (int v : adj[i]) {
                        if (v == j) {
                            has_edge = true;
                            break;
                        }
                    }
                    if (!has_edge) {
                        cout << i << " " << j << endl;
                        cout << flush;
                        goto read_opponent;
                    }
                }
            }
        }
read_opponent:
        int x, y;
        cin >> x >> y;
        if (x == -1 && y == -1) break;
    }
    return 0;
}

Submission Info

Judge Result