#include "speedrun.h"
#include <bits/stdc++.h>

constexpr int LG = 10;

void dfs(
  int node,
  std::vector<int> &par,
  std::vector<int> &id,
  std::vector<int> &t,
  const std::vector<std::vector<int>> &adj
) {
  t.push_back(node);
  id[node] = static_cast<int>(t.size()) - 1;
  for (int i : adj[node]) {
    if (i == par[node]) {
      continue;
    }
    par[i] = node;
    dfs(i, par, id, t, adj);
  }
}

void assignHints(int /*subtask*/, int N, int A[], int B[]) {
  const int n = N;
  std::vector<std::vector<int>> adj(n + 1);
  for (int i = 1; i < n; ++i) {
    adj[A[i]].push_back(B[i]);
    adj[B[i]].push_back(A[i]);
  }
  std::vector<int> par(n + 1, -1), id(n + 1, -1), t;
  dfs(1, par, id, t, adj);

  setHintLen(2 * LG);
  for (int i = 1; i <= n; ++i) {
    if (par[i] != -1) {
      for (int j = 0; j < LG; ++j) {
        setHint(i, j, ((1 << j) & par[i]) != 0);
      }
    }
    if (id[i] != n - 1) {
      int nxt = t[id[i] + 1];
      for (int j = 0; j < LG; ++j) {
        setHint(i, j + LG, ((1 << j) & nxt) != 0);
      }
    }
  }
  for (int i = 1; i <= n; ++i) {
    std::cerr << par[i] << ' ';
  }
  std::cerr << '\n';
}

int get_par() {
  int ans = 0;
  for (int j = 0; j < LG; ++j) {
    if (getHint(j)) {
      ans |= 1 << j;
    }
  }
  return ans;
}

int get_nxt() {
  int ans = 0;
  for (int j = 0; j < LG; ++j) {
    if (getHint(j + LG)) {
      ans |= 1 << j;
    }
  }
  return ans;
}

void speedrun(int /*subtask*/, int N, int start) {
  const int n = N;
  int node = start;
  while (node != 1) {
    node = get_par();
    bool b = goTo(node);
    assert(b);
  }

  std::stack<int, std::vector<int>> st;
  st.push(1);
  for (int i = 1; i < n; ++i) {
    int nxt = get_nxt();
    while (!st.empty()) {
      if (goTo(nxt)) {
        st.push(nxt);
        break;
      }
      st.pop();
      bool b = goTo(st.top());
      assert(b);
    }
  }
}

speedrun.code:4:1: error: ‘constexpr’ does not name a type
    4 | constexpr int LG = 10;
      | ^~~~~~~~~
speedrun.code:4:1: note: C++11 ‘constexpr’ only available with ‘-std=c++11’ or ‘-std=gnu++11’
speedrun.code:11:36: error: ‘>>’ should be ‘> >’ within a nested template argument list
   11 |   const std::vector<std::vector<int>> &adj
      |                                    ^~
      |                                    > >
speedrun.code: In function ‘void dfs(int, std::vector<int>&, std::vector<int>&, std::vector<int>&, const std::vector<std::vector<int> >&)’:
speedrun.code:15:16: warning: range-based ‘for’ loops only available with ‘-std=c++11’ or ‘-std=gnu++11’
   15 |   for (int i : adj[node]) {
      |                ^~~
speedrun.code:15:24: error: forming reference to reference type ‘const std::vector<int>&’
   15 |   for (int i : adj[node]) {
      |                        ^
speedrun.code: In function ‘void assignHints(int, int, int*, int*)’:
speedrun.code:26:30: error: ‘>>’ should be ‘> >’ within a nested template argument list
   26 |   std::vector<std::vector<int>> adj(n + 1);
      |                              ^~
      |                              > >
speedrun.code:34:18: error: ‘LG’ was not declared in this scope
   34 |   setHintLen(2 * LG);
      |                  ^~
speedrun.code: In function ‘int get_par()’:
speedrun.code:56:23: error: ‘LG’ was not declared in this scope
   56 |   for (int j = 0; j < LG; ++j) {
      |                       ^~
speedrun.code: In function ‘int get_nxt()’:
speedrun.code:66:23: error: ‘LG’ was not declared in this scope
   66 |   for (int j = 0; j < LG; ++j) {
      |                       ^~
speedrun.code: In function ‘void speedrun(int, int, int)’:
speedrun.code:83:34: error: ‘>>’ should be ‘> >’ within a nested template argument list
   83 |   std::stack<int, std::vector<int>> st;
      |                                  ^~
      |                                  > >
grader_speedrun.cpp: In function ‘int readvalue()’:
grader_speedrun.cpp:9:9: warning: ignoring return value of ‘int fscanf(FILE*, const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
    9 |   fscanf(input, "%d", &val);
      |   ~~~~~~^~~~~~~~~~~~~~~~~~~