Забавная игра

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <set>
#include <stack>
#include <bitset>
#include <map>
#include <ctime>
#include <numeric>


#ifndef M_PI
#define M_PI 3.141592653589
#endif
#define int long long
#define double long double

#ifdef TIME
#define start cin.tie(NULL); cout.tie(NULL); cout.setf(ios::fixed); cout.precision(10); ios_base::sync_with_stdio(false);int32_t START = clock()
#define finish cout << "\ntime: " << (clock() - START) / (CLOCKS_PER_SEC * 1.0); return 0
#endif

#ifndef TIME
#define start cin.tie(NULL); cout.tie(NULL); cout.setf(ios::fixed); cout.precision(10); ios_base::sync_with_stdio(false)
#define finish return 0
#endif

using namespace std;


//vector input
template<typename T>
istream &operator>>(istream &is, vector<T> &vec) {
    for (auto &i : vec) {
        cin >> i;
    }
    return is;
}

//pair output
template<typename E>
ostream &operator<<(ostream &os, pair<E, E> &t) {
    os << t.first << ' ' << t.second;
    return os;
}

//"map" pair output
template<typename E>
ostream &operator<<(ostream &os, pair<const E, E> &t) {
    os << t.first << ' ' << t.second;
    return os;
}

//vector output
template<typename T>
ostream &operator<<(ostream &os, vector<T> &vec) {
    for (T i : vec) {
        os << i << ' ';
    }
    return os;
}

//2 dimensional vector output
template<typename T>
ostream &operator<<(ostream &os, vector<vector<T> > &vec) {
    for (vector<T> i : vec) {
        os << i << '\n';
    }
    return os;
}

vector<vector<int>> incorg;
vector<vector<int>> rg;
vector<vector<int>> g;
vector<int> deq;
vector<int> ans;

void dfs(int v, int p) {
    for (auto u : incorg[v]) {
        if (u != p) {
            g[v].push_back(u);
            dfs(u, v);
        }
    }
}

int32_t main() {
    start;

    int n, k;
    cin >> n >> k;
    incorg.assign(n, vector<int>());
    rg.assign(n, vector<int>());
    deq.assign(n, 0);
    ans.assign(n, 0);
    g.resize(n);

    for (int i = 0; i < n - 1; ++i) {
        int from, to;
        cin >> from >> to;
        incorg[from - 1].push_back(to - 1);
        incorg[to - 1].push_back(from - 1);
    }

    dfs(k - 1, k - 1);

    for (int i = 0; i < n; ++i) {
        for (auto v : g[i]) {
            rg[v].push_back(i);
            deq[i] += 1;
        }
    }

    queue<int> q;

    for (int i = 0; i < n; ++i) {
        if (deq[i] == 0) {
            ans[i] = 1;
            q.push(i);
        }
    }

    while (!q.empty()) {
        int v = q.front();
        q.pop();
        if (ans[v] == 1) {
            for (auto u : rg[v]) {
                if (ans[u] == 0) {
                    ans[u] = 2;
                    q.push(u);
                }
            }
        } else if (ans[v] == 2) {
            for (auto u : rg[v]) {
                deq[u] -= 1;
                if (deq[u] == 0 && ans[u] == 0) {
                    ans[u] = 1;
                    q.push(u);
                }
            }
        }
    }

    if (ans[k - 1] != 2) {
        cout << "First player loses" << '\n';
    } else {
        int mn = INT64_MAX;
        for (auto u : g[k - 1]) {
            if (ans[u] == 1) {
                mn = min(mn, u);
            }
        }
        cout << "First player wins flying to airport" << " " << mn + 1 << '\n';
    }


    finish;
}