#include "validation.h"
using std::vector;
using std::pair;
using std::set;
using std::cbrt;

// A validator. It checks if all consecutive vertices in the answer are at distance of at most three as follows:
//
// Categorize vertices into those with large degree and those with small degree with border value c = sqrt_3(m^2/n).
// For every large degree vertex, determine the set of all nodes at distance 2 with a BFS. This takes O(m) time per large degree vertex.
// Since the total degree is O(m), there are at most O(m/c) = O(sqrt_3(mn)) large degree vertices.
// Thus, this step takes O(sqrt_3(m^4n)) time total.
//
// Now, for every pair of consecutive vertices in the anwer, do the following:
// If one of the nodes has large degree, then check for each neighbor of the other node if it occurs in the distance-2-set of the large node.
// This takes O(size-of-neighborhood) time for each check and thus O(m) time over all checks of this form.
// If both nodes have small degree, then check for each neighbor of the first vertex and each neighbor of the second vertex if there is an edge between them.
// This takes O(size-of-first-neighborhood * size-of-second-neighborhood) time for each check.
// Since both nodes have small degree, this is O(sqrt_3(m^4/n^2)). Since there are at most n checks, this is O(sqrt_3(m^4n)) time overall.
//
// In total, the validator runs in O(sqrt_3(m^4n)) time which is doable for m,n < 2*10^5.

int main(int argc, char **argv) {
    // Set up the input and answer streams.
    std::ifstream in(argv[1]);
    std::ifstream ans(argv[2]); // Only for custom checker.
    OutputValidator v(argc, argv);

    // Read graph
    int n,m;
    in >> n >> m;
    vector<vector<int>> graph(n,vector<int>{});
    set<pair<int,int>> edges;
    for (int i=0;i<m;i++) {
        int x,y;
        in >> x >> y;
        x--; y--;
        graph[x].push_back(y);
        graph[y].push_back(x);
        edges.insert({x,y});
        edges.insert({y,x});
    }

    // Compute large and small degree vertices
    int c = cbrt(m*m/n);
    vector<bool> is_large(n,false);
    for (int i=0;i<n;i++) is_large[i] = graph[i].size() > c;

    // Precompute distance 2 sets
    vector<set<int>> N2(n,set<int>{});
    for (int i=0;i<n;i++) if (is_large[i]) {
        for (int j : graph[i]){
            N2[i].insert(j);
            for (int k : graph[j]) N2[i].insert(k);
        }
    }

    // Read team answer
    vector<long long> answer = v.read_integers("answer", n, 1, n, Unique);

    // Check team answer
    for (int i=0;i<n-1;i++) {
        int x = (int)answer[i]-1;
        int y = (int)answer[i+1]-1;
        bool valid = false;

		// `contains` only works in C++20
        // if (edges.contains({x,y})) { // edge case: vertices are adjacent
        if (edges.find({x,y}) != edges.end()) { // edge case: vertices are adjacent
            valid=true;
        }
        else if (is_large[x]) { // left node has large degree
            // `contains` only works in C++20
            // for (int z : graph[y]) if (N2[x].contains(z)) {
            for (int z : graph[y]) if (N2[x].find(z) != N2[x].end()) {
                valid=true;
                break;
            }
        }
        else if (is_large[y]) { // right node has large degree
            // `contains` only works in C++20
            // for (int z : graph[x]) if (N2[y].contains(z)) {
            for (int z : graph[x]) if (N2[y].find(z) != N2[y].end()) {
                valid=true;
                break;
            }
        }
        else { // both nodes have small degree
            for (int z1 : graph[x]) for (int z2 : graph[y]) {
                // `contains` only works in C++20
                // if (z1==z2 or edges.contains({z1,z2})) {
                if (z1==z2 or edges.find({z1,z2}) != edges.end()) {
                    valid=true;
                    break;
                }
            }
        }
        v.check(valid, "vertices ", x+1, " and ", y+1, " are too far apart");
    }

    return 0;
}