#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
struct State {
int node, prev;
};
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
// Build adjacency with beauty order
vector<vector<int>> adj(N);
for (int i = 0; i < M; i++) {
int u = R[i][0], v = R[i][1];
adj[u].push_back(v);
adj[v].push_back(u);
}
// For each node, we already know adjacency list is in order of beauty,
// since trails were given in decreasing beauty order.
// So the first neighbor in adj[u] is the most beautiful, second is 2nd most.
// (If more than 2 neighbors, we only care about the first 2.)
vector<int> best(N, -1), second(N, -1);
for (int u = 0; u < N; u++) {
if (!adj[u].empty()) best[u] = adj[u][0];
if (adj[u].size() >= 2) second[u] = adj[u][1];
}
// Answer queries one by one (Q = 1 in Subtask 1 anyway)
for (int qi = 0; qi < Q; qi++) {
int K = G[qi];
long long result = 0;
// BFS/DP: state = (current node, previous node), step number
map<pair<int,int>, long long> cur, nxt;
// initial: can start from any node, with prev = -1
for (int u = 0; u < N; u++) {
cur[{u, -1}] = 1;
}
for (int step = 0; step < K; step++) {
nxt.clear();
for (auto &entry : cur) {
int u = entry.first.first;
int prev = entry.first.second;
long long ways = entry.second;
// Choose next neighbor according to rules
int go = -1;
if (best[u] != -1 && best[u] != prev) {
go = best[u];
} else if (second[u] != -1 && second[u] != prev) {
go = second[u];
} else {
// must go back to prev
go = prev;
}
nxt[{go, u}] += ways;
}
cur.swap(nxt);
}
// Count how many end at P
for (auto &entry : cur) {
int u = entry.first.first;
long long ways = entry.second;
if (u == P) result += ways;
}
answer(result);
}
}
