//経路復元付きBFS
//resizeを忘れないようにする
//s->tの経路が存在しないのにrestore関数を呼び出したときの挙動は未定義です
vector<vector<long long>> G;
vector<long long> preview;
//始点startからX回以内の移動でたどりつける頂点の最短距離を求める(到達できないなら-1)
void bfs(vector<long long> &dist, long long X, long long start)
{
    queue<long long> que;
    dist[start] = 0;
    preview[start] = -1;
    que.push(start);
    while (!que.empty())
    {
        long long v = que.front();
        que.pop();
        if (dist[v] == X)
            continue;
        for (auto next_v : G[v])
        {
            if (dist[next_v] != -1)
                continue;
            preview[next_v] = v;
            dist[next_v] = dist[v] + 1;
            que.push(next_v);
        }
    }
}
//BFS後、頂点xへの最短経路のうち1つを復元する(0-indexedかつ0番目からstart->endの順にindexを格納)
vector<long long> restore(long long x)
{
    vector<long long> ret;
    for (long long i = x; i != -1; i = preview[i])
    {
        ret.push_back(i);
    }
    reverse(ret.begin(), ret.end());
    return ret;
}