#include <cassert>
#include <cctype>
// #include <cerrno>
#include <cfloat>
// #include <ciso646>
#include <climits>
// #include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
// #include <cstdalign>
// #include <cstdbool>
#include <cstdint>
// #include <ctgmath>
// #include <cuchar>
// #include <cwchar>
// #include <cwctype>
#endif //__cplusplus >= 201103L

// C++ headers
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
// #include <atomic>
#include <chrono>
// #include <codecvt>
// #include <condition_variable>
#include <forward_list>
// #include <future>
#include <initializer_list>
// #include <mutex>
#include <random>
#include <ratio>
#include <regex>
// #include <scoped_allocator>
#include <system_error>
// #include <thread>
#include <tuple>
// #include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif //__cplusplus >= 201103L

#if __cplusplus >= 201402L
#include <shared_mutex>
#endif //__cplusplus >= 201402L

using namespace std;
struct initon {
    initon() {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout.setf(ios::fixed);
        cout.precision(16);
        srand((unsigned) clock() + (unsigned) time(NULL));
    };
} initonv;

//@メタ meta
//template<class T, require_t(is_same<T, U>::value)>等
#define require_t(bo) enable_if_t<bo>* = nullptr
template<typename T, typename U = typename T::value_type> std::true_type value_type_tester(signed);

template<typename T> std::false_type value_type_tester(long);
template<typename T> struct has_value_type : decltype(value_type_tester<T>(0)) {};
template<class T> inline constexpr bool has_value_type_v = has_value_type<T>::value;

template<class T> struct is_vector : std::false_type {};
template<class T> struct is_vector<std::vector<T>> : std::true_type {};
template<class T> inline constexpr bool is_vector_v = is_vector<T>::value;

template<class T1, class T2, bool t1_bigger = (sizeof(T1) > sizeof(T2))> struct max_type { typedef T1 type; };
template<class T1, class T2> struct max_type<T1, T2, false> { typedef T2 type; };

//A<T>でTを返す
template<class T> using value_type_t = typename T::value_type;
//A<B<.....T>>でTを返す
template<class T, bool end = !has_value_type<T>::value> struct value_type_rec { typedef T type; };
template<class T> struct value_type_rec<T, false> { typedef typename value_type_rec<value_type_t<T>>::type type; };
template<class T> using value_type_rec_t = typename value_type_rec<T>::type;

//int == remove_extent_rec_t<int[][][]>
template<class T, bool end = is_same<T, remove_extent_t<T>>::value> struct remove_extent_rec { typedef T type; };
template<class T> struct remove_extent_rec<T, false> { typedef typename remove_extent_rec<remove_extent_t<T>>::type type; };
template<class T> using remove_extent_rec_t = typename remove_extent_rec<T>::type;
//^@メタ meta


//別名置換
#define int long long
#define ll long long
using vb = vector<bool>;
using vc = vector<char>;
using vi = vector<int>;
using vs = vector<string>;
#define sz(a) ((ll)(a).size())
#define k4 10101
#define k5 101010
#define k6 1010101
#define k7 10101010
const double PI = 3.1415926535897932384626433832795029L;
const double eps = 1e-9;
using str = string;
using P = pair<ll, ll>;
using T = tuple<ll, ll, ll>;
using F = tuple<ll, ll, ll, ll>;
#define uset unordered_set
#define mset multiset
#define umap unordered_map

//#define V vector
#define vvt0(t) vector<vector<t>>
#define vvt1(t, a) vector<vector<t>>a
#define vvt2(t, a, b) vector<vector<t>>a(b)
#define vvt3(t, a, b, c) vector<vector<t>> a(b,vector<t>(c))
#define vvt4(t, a, b, c, d) vector<vector<t>> a(b,vector<t>(c,d))

#define vv(type, ...) over4(__VA_ARGS__,vvt4,vvt3,vvt2 ,vvt1,vvt0)(type,__VA_ARGS__)
#define vvi(...) vv(ll,__VA_ARGS__)
#define vvb(...) vv(bool,__VA_ARGS__)
#define vvs(...) vv(string,__VA_ARGS__)
#define vvd(...) vv(double,__VA_ARGS__)
#define vvc(...) vv(char,__VA_ARGS__)
#define vvp(...) vv(P,__VA_ARGS__)
#define vvt(...) vv(T,__VA_ARGS__)

//記述をシンプルにする
#define over2(o1, o2, name, ...) name
#define over3(o1, o2, o3, name, ...) name
#define over4(o1, o2, o3, o4, name, ...) name
#define over5(o1, o2, o3, o4, o5, name, ...) name
#define over6(o1, o2, o3, o4, o5, o6, name, ...) name


//@ループ
#define over4(o1, o2, o3, o4, name, ...) name
#define rep1(n) for(ll rep1i = 0,rep1lim=n; rep1i < rep1lim ; ++rep1i)
#define rep2(i, n) for(ll i = 0,i##rep2lim=n; i < i##rep2lim ; ++i)
#define rep3(i, m, n) for(ll i = m,i##rep3lim=n; i < i##rep3lim ; ++i)
#define rep4(i, m, n, ad) for(ll i = m,i##rep4lim=n; i < i##rep4lim ; i+= ad)
#define rep(...) over4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)

//逆順 閉区間
#define rer2(i, n) for(ll i = n; i >= 0 ; i--)
#define rer3(i, m, n) for(ll i = m,i##rer3lim=n; i >= i##rer3lim ; i--)
#define rer4(i, m, n, dec) for(ll i = m,i##rer4lim=n; i >= i##rer4lim ; i-=dec)
#define rer(...) over4(__VA_ARGS__,rer4,rer3,rer2,)(__VA_ARGS__)

constexpr ll inf = (ll) 1e9 + 100;
constexpr ll linf = (ll) 1e18 + 100;
constexpr double dinf = (double) linf * linf;

template<typename T> class fixed_point
        : T {
public:
    explicit constexpr fixed_point(T &&t) noexcept: T(std::forward<T>(t)) {}
    template<typename... Args> constexpr decltype(auto) operator()(Args &&... args) const { return T::operator()(*this, std::forward<Args>(args)...); }
};
template<typename T> static inline constexpr decltype(auto) fix(T &&t) noexcept { return fixed_point<T>{std::forward<T>(t)}; }
//初期値l=-1, r=-1
void set_lr12(int &a, int &b, int n) {    /*b==-1*/    if (b == -1) {
        if (a == -1) {
            a = 0;
            b = n;
        } else {
            b = a;
            a = 0;
        }
    }
}

template<class T, class U> bool chma(T &a, const U &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template<class T, class U> bool chmi(T &a, const U &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
template<class T> T MAX() { return numeric_limits<T>::max(); }
template<class T> T MIN() { return numeric_limits<T>::min(); }

template<typename W, typename T> void fill(vector<W> &a, const T &v, int l = -1, ll r = -1) {
    set_lr12(l, r, a.size());
    if constexpr(!is_vector<W>::value) { rep(i, l, r)a[i] = v; } else { rep(i, l, r)fill(a[i], v); }
}
template<class Iterable, require_t(has_value_type_v<Iterable>)> value_type_rec_t<Iterable> sum(const Iterable &a, int l = -1, int r = -1) {
    value_type_rec_t<Iterable> ret = 0;    /*vectorの処理*/    if constexpr(is_vector_v<Iterable>) { set_lr12(l, r, sz(a));        /*1次元なら全部足す*/        if constexpr(!has_value_type_v<value_type_t<Iterable>>) { rep(i, l, r) ret += a[i]; } else { rep(i, l, r) ret += sum(a[i]); }} else {        /*set等の処理*/        if constexpr(!has_value_type_v<value_type_t<Iterable>>) { for (auto &v : a) { ret += v; }} else { for (auto &v : a) { ret += sum(v); }}}
    return ret;
}
template<class Iterable, require_t(has_value_type_v<Iterable>)> value_type_rec_t<Iterable> min(const Iterable &a, int l = -1, int r = -1) {
    value_type_rec_t<Iterable> ret = MAX<value_type_rec_t<Iterable>>();    /*vectorの処理*/    if constexpr(is_vector_v<Iterable>) { set_lr12(l, r, sz(a));        /*1次元なら全部足す*/        if constexpr(!has_value_type_v<value_type_t<Iterable>>) { rep(i, l, r) ret = min(ret, a[i]); } else { rep(i, l, r) ret = min(ret, min(a[i])); }} else {        /*set等の処理*/        if constexpr(!has_value_type_v<value_type_t<Iterable>>) { for (auto &v : a) { ret = min(ret, v); }} else { for (auto &v : a) { ret = min(ret, min(v)); }}}
    return ret;
}
template<class Iterable, require_t(has_value_type_v<Iterable>)> value_type_rec_t<Iterable> max(const Iterable &a, int l = -1, int r = -1) {value_type_rec_t<Iterable> ret = MIN<value_type_rec_t<Iterable>>();    /*vectorの処理*/    if constexpr(is_vector_v<Iterable>) {        set_lr12(l, r, sz(a));        /*1次元なら全部足す*/        if constexpr(!has_value_type_v<value_type_t<Iterable>>){            rep(i, l, r) ret = max(ret, a[i]);        }else{            rep(i, l, r) ret = max(ret, max(a[i]));        }    }    else {        /*set等の処理*/        if constexpr(!has_value_type_v<value_type_t<Iterable>>){            for (auto &v : a) { ret = max(ret, v); }        }else{            for (auto &v : a) { ret = max(ret, max(v)); }        }    }    return ret;}/*@formatter:off*/

template<class Array, class T, size_t N> void fill(Array(&a)[N] , const T& v, int l = -1, int r = -1) {    set_lr12(l, r, N);    if constexpr(is_same_v<Array, remove_extent_t<Array>>){        rep(i, l, r) a[i] = v;    }else{        rep(i, l, r) fill(a[i], v);    }}
template<class Array, size_t N> remove_extent_rec_t<Array> sum(const Array(&a)[N] , int l = -1, int r = -1) {    remove_extent_rec_t<Array> ret = 0;    set_lr12(l, r, N);    if constexpr(is_same_v<Array, remove_extent_t<Array>>){        rep(i, l, r) ret += a[i];    }else{        rep(i, l, r) ret += sum(a[i]);    }    return ret;}
template<class Array, size_t N> remove_extent_rec_t<Array> min(const Array(&a)[N] , int l = -1, int r = -1) {    remove_extent_rec_t<Array> ret = MAX<remove_extent_rec_t<Array>>();    set_lr12(l, r, N);    if constexpr(is_same_v<Array, remove_extent_t<Array>>){        rep(i, l, r) ret = std::min(ret, a[i]);    }else{        rep(i, l, r) ret = std::min(ret, min(a[i]));    }    return ret;}
template<class Array, size_t N> remove_extent_rec_t<Array> max(const Array(&a)[N] , int l = -1, int r = -1) {    remove_extent_rec_t<Array> ret = MIN<remove_extent_rec_t<Array>>();    set_lr12(l, r, N);    if constexpr(is_same_v<Array, remove_extent_t<Array>>){        rep(i, l, r) ret = std::max(ret, a[i]);    }else{        rep(i, l, r) ret = std::max(ret, max(a[i]));    }    return ret;}
template<class T> void na(vector<T> &A, int N) {A.resize(N);for (int i = 0; i < N; i++) { cin >> A[i]; }}
#define fora(a, A) for(auto& a : A)
#define ALL(A) (A).begin(), (A).end()

template<class T, class U> pair<T, U> operator+=(pair<T,U> &a, const pair<T,U> & b) {a.fi+=b.fi;a.se+=b.se; return a;}
template<class T, class U> pair<T, U> operator+(const pair<T, U> &a, const pair<T, U> &b) { pair<T, U> c = a;c += b;return c;}

template<class T, class U> pair<T, U> operator-=(pair<T,U> &a, const pair<T,U> & b) {a.fi-=b.fi;a.se-=b.se; return a;}
template<class T, class U> pair<T, U> operator-(const pair<T, U> &a, const pair<T, U> &b) { pair<T, U> c = a;c -= b;return c;}

template<class T, class U, class V> pair<T, U> operator*=(pair<T, U> &a, const V& b) { a.fi*=b;a.se*=b; return a;}
template<class T, class U, class V> pair<T, U> operator*(const pair<T, U> &a, const V& b) { pair<T, U> c = a;c *= b;return c; }

template<class T, class U, class V> pair<T, U> operator/=(pair<T, U> &a, const V& b) { a.fi/=b;a.se/=b; return a;}
template<class T, class U, class V> pair<T, U> operator/(const pair<T, U> &a, const V& b) { pair<T, U> c = a;c /= b;return c; }

template<class T, class U> pair<T, U> operator-(const pair<T, U> &a) { return pair<T, U>(-a.first, -a.second); }

/*@formatter:on*/
#define deb(...)
#define endl '\n'
//int inf = 1<<30;
//long long linf = 1ll<<60;
//double  dinf = 1ll<<60;
//#define assert2(...)

namespace {/*@formatter:off*/
    template<class T> T INF() { return numeric_limits<T>::max() / 2; }
    template<> signed INF() { return inf; }
    template<> ll INF() { return linf; }
    template<> double INF() { return dinf; }
    template<> char INF() { return '{'; }
    template<> string INF() { return "{"; }
    void ole() {
#ifdef _DEBUG
        cerr << "ole" << endl;exit(0);
#endif
        string a = "a";    rep(i, 30)a += a;    rep(i, 1 << 17)cout << a << endl;    cout << "OLE 出力長制限超過" << endl;exit(0);
    }
    void re(string s = "") {cerr << s << endl;assert(0 == 1);exit(0);}

    void tle() { while (inf)cout << inf << endl; }
#undef getid
#undef getid_1
#undef getid_2

#define forg_f_init(ve) int f = ve[gi].f, t = ve[gi].t; auto& c = ve[gi].c
#define forg_f(gi, ve) for (ll gi = 0,forg_flim = ve.size(); gi < forg_flim; ++gi)

#define fort_f(gi, ve) for (ll gi = 0,forg_flim = ve.size(); gi < forg_flim ; ++gi)
#define fort_f_init(gi, ve) int f = ve[gi].f, t = ve[gi].t, c = ve[gi].c;if(t == p)continue;
#define fore(gi, ve) for (ll gi = 0,forg_flim = ve.size(), f, t, c; gi < forg_flim && (f = ve[gi].f, t = ve[gi].t, c = ve[gi].c, true); ++gi)
    template<class T> struct edge_ {
        typedef T value_type;
        int f, t;
        T c;
        edge_(int f, int t, T c = 1) : f(f), t(t), c(c) {}
        bool operator<(const edge_ &b) const { return c < b.c; }
        bool operator>(const edge_ &b) const { return c > b.c; }
    };
    template<class T> ostream &operator<<(ostream &os, edge_<T> &e) {os << e.f << " " << e.t << " " << e.c;return os;}
    template<typename T> class graph {
    public :
        typedef T value_type;
        vector<vector<edge_<T>>> g;
        vector<edge_<T>> edges;
        int n;
        explicit graph(int n) : n(n) { g.resize(n); }
        void clear() { g.clear(), edges.clear(); }
        void resize(int n) {this->n = n;g.resize(n);}
        int size() { return n; }
        vector<edge_<T> > &operator[](int i) { return g[i]; }
        virtual void add(int f, int t, T c) = 0;
        virtual void set_edges() = 0;
    };
    template<typename T =ll> class digraph : public graph<T> {
    public:
        using graph<T>::g;
        using graph<T>::n;
        using graph<T>::edges;
        explicit digraph(int n) : graph<T>(n) {}
        explicit digraph(int n, const vector<edge_<T>>& E) : graph<T>(n) {        fora(e,E){            add(e.f,e.t,e.c);        }    }
        void add(int f, int t, T c = 1) {
            if (!(0 <= f && f < n && 0 <= t && t < n)) {cerr<<"digraph add"<<endl;deb(f, t, c);ole();}
            g[f].emplace_back(f, t, c);
            edges.emplace_back(f, t, c);//edgesを使わないなら消せる
        }
        void ing(int n, int m, int minus = 1) {        this->resize(n);        rep(i, m) {            int f, t;            cin >> f >> t;            f -= minus;            t -= minus;            add(f, t);        }    }
        void ingc(int n, int m, int minus = 1) {        this->resize(n);        rep(i, m) {            int f, t, c;            cin >> f >> t >> c;            f -= minus;            t -= minus;            add(f, t, c);        }    }
        void set_edges() override{        if (sz(edges))return;        rep(i, n)fora(e, g[i])edges.push_back(e);    }
    };
#define unionfind unionfind_graph
    struct unionfind {
        vector<ll> par;
        vector<ll> siz;
        vector<ll> es;
        ll n, trees;//連結グループの数(親の種類)
        unionfind(ll n) : n(n), trees(n) {        par.resize(n);        siz.resize(n);        es.resize(n);        for (ll i = 0; i < n; i++) {            par[i] = i;            siz[i] = 1;        }    }
        template<class T>unionfind(graph<T>& g) : n(g.n), trees(g.n) {        par.resize(n);        siz.resize(n);        es.resize(n);        for (ll i = 0; i < n; i++) {            par[i] = i;            siz[i] = 1;        }        add(g);    }
        ll root(ll x) { if (par[x] == x) { return x; } else { return par[x] = root(par[x]); }}
        ll operator()(ll x){return root(x);}
        bool unite(ll x, ll y) {            x = root(x);            y = root(y);            es[x]++;            if (x == y) return false;            if (siz[x] > siz[y]) swap(x, y);            trees--;            par[x] = y;            siz[y] += siz[x];            es[y] += es[x];            return true;        }
        template<class T>void add(graph<T>&g){fora(e,g.edges){unite(e.f,e.t);}}
        template<class T>void unite(graph<T>&g){add(g);}
        bool same(ll x, ll y) { return root(x) == root(y); }
        ll size(ll x) { return siz[root(x)]; }
        ll esize(ll x) { return es[root(x)]; }
        vi sizes(){        vi cou(n);        vi ret;        ret.reserve(n);        rep(i, n){            cou[root (i)]++;        }        rep(i, n){            if(cou[i])ret.push_back(cou[i]);        }        return ret;    }
        //つながりを無向グラフと見なし、xが閉路に含まれるか判定
        bool close(ll x) { return esize(x) >= size(x); }
        vector<vi> sets() {        vi ind(n, -1);        ll i = 0;        vvi(res, trees);        rep(j, n) {            ll r = root(j);            if (ind[r] == -1)ind[r] = i++;            res[ind[r]].push_back(j);        }        rep(i, trees) {            ll r = root(res[i][0]);            if (res[i][0] == r)continue;            rep(j, 1, sz(res[i])) {                if (res[i][j] == r) {                    swap(res[i][0], res[i][j]);                    break;                }            }        }        return res;    }
    };//@formatter:off

#define UNDIG_WITH_UNIONFIND

    template<class T=int> class undigraph : public graph<T> {
    public:
        using graph<T>::g;    using graph<T>::n;    using graph<T>::edges;
#ifdef UNDIG_WITH_UNIONFIND
        //頂点の連結
        //属するサイズ
        //連結している辺の数などが分かる
        unionfind uf;
        explicit undigraph(int n) : graph<T>(n), uf(n) {}
        explicit undigraph(int n, const vector<edge_<T>>& E) : graph<T>(n), uf(n) {        fora(e,E){            add(e.f,e.t,e.c);       uf.unite(e.f, e.t); }    }
#else
        explicit undigraph(int n) : graph<T>(n) {}
        explicit undigraph(int n, const vector<edge_<T>>& E) : graph<T>(n) {        fora(e,E){            add(e.f,e.t,e.c);        }    }
#endif
        // f < t
        void add(int f, int t, T c = 1) {
            if (!(0 <= f && f < n && 0 <= t && t < n)) {            cerr<<("undigraph add")<<endl;            deb(f, t, c);            ole();        }
            g[f].emplace_back(f, t, c);
            g[t].emplace_back(t, f, c);
            edges.emplace_back(f, t, c);//edgesを使わないなら消せる
            edges.emplace_back(t, f, c);
#ifdef UNDIG_WITH_UNIONFIND
            uf.unite(f, t);
#endif
        }
        void add(edge_<T> &e) {        int f = e.f, t = e.t;        T c = e.c;        add(f, t, c);    }
        void ing(int n, int m, int minus = 1) {        this->resize(n);        rep(i, m) {            int f, t;            cin >> f >> t;            f -= minus;            t -= minus;            add(f, t);        }    }
        void ingc(int n, int m, int minus = 1) {        this->resize(n);        rep(i, m) {            int f, t, c;            cin >> f >> t >> c;            f -= minus;            t -= minus;            add(f, t, c);        }    }
        void set_edges () override{        if (sz(edges))return;        rep(i, n)fora(e, g[i])edges.push_back(e);    }
        //iを含む、連結成分を返す
        vector<int> sames(int i){            vector<int> nodes;            unordered_set<int> was;            queue<int> q;            q.push(i);            was.insert(i);            nodes.push_back(i);            while(!q.empty()){                int i = q.front();                q.pop();                for(auto& e : g[i]){                    if(was.find(e.t) != was.end())continue;                    was.insert(e.t);                    nodes.push_back(e.t);                    q.push(e.t);                }            }            return nodes;        }

#ifdef UNDIG_WITH_UNIONFIND
        using graph<T>::size;
        int root_uf(int i){return uf.root(i);}
        //iの連結連結成分のサイズを返す
        int size(int i){return uf.size(i);}
        int esize(int i){return uf.esize(i);}
        bool same(int i, int j){return uf.same(i, j);}
        //iの連結成分がなもりグラフ(n頂点n辺)かを返す
        bool is_namori(int i){return uf.size(i) == uf.esize(i);}
        bool is_namori() {return uf.size(0) == n && uf.esize(0) == n;}
#endif
    };

#define dijkstra_path dis_path
    template<class T,class I> vi dis_path(digraph<T> &g, vector<T> &dis, int s, int t, I init_value) {    assert(dis[t] != init_value);    auto rg = rev(g);    int now = t;    vi path;    path.push_back(now);    T cost = 0;    while (now != s) {        rep(gi, sz(rg[now])) {            int m = rg[now][gi].t;            if (dis[m] == init_value)continue;            if (dis[m] + rg[now][gi].c + cost == dis[t]) {                cost += rg[now][gi].c;                now = m;                break;            }        }        path.push_back(now);    }    std::reverse(path.begin(), path.end());    return path;}
    template<class T,class I> vi dis_path(undigraph<T> &g, vector<T> &dis, int s, int t, I init_value) {    assert(dis[t] != init_value);    int now = t;    vi path;    path.push_back(now);    T cost = 0;    while (now != s) {        rep(gi, sz(g[now])) {            int m = g[now][gi].t;            if (dis[m] == init_value)continue;            if (dis[m] + g[now][gi].c + cost == dis[t]) {                cost += g[now][gi].c;                now = m;                break;            }        }        path.push_back(now);    }    reverse(path.begin(), path.end());    return path;}
    template<class T,class I> vi dis_path(digraph<T> &g, vector<vector<T>> &dis, int s, int t, I init_value) { return dis_path(g, dis[s], s, t, init_value); }
    template<class T,class I> vi dis_path(undigraph<T> &g, vector<vector<T>> &dis, int s, int t, I init_value) { return dis_path(g, dis[s], s, t, init_value); }
    vi to_vi(const int& i){return vi{i};}
    vi to_vi(const vi& v){return v;}
#define dijk dijkstra
//O(N^2)
    template<class T, class U, class I> vector<T> dijkstra_mitu(graph<T> &g, const U &S_, I init_value) {    vi S = to_vi(S_);    int n = g.n;    T initValue = numeric_limits<T>::max();    vector<T> dis(n, initValue);    fora(s, S) {        if (!(0 <= s && s < g.n)) {            cerr<<("dijkstra_mitu")<<endl;            deb(s, g.n);            ole();        }        dis[s] = 0;    }    vb used(n);    while (true) {        int v = -1;        rep(u, n) { if (!used[u] && (v == -1 || dis[u] < dis[v]))v = u; }        if (v == -1)break;        if (dis[v] == initValue)break;        used[v] = true;        rep(u, sz(g[v])) {            auto e = g[v][u];            dis[e.t] = min(dis[e.t], dis[v] + e.c);        }    }    /*基本、たどり着かないなら-1*/    for (auto &&d :dis) { if (d == initValue) { d = init_value; }}    return dis;}
    template<class T, class U, class I> vector<T> dijkstra_01(graph<T> &g, const U &S_, I init_value) {int N = g.n;    vi S = to_vi(S_);    T tinf = INF<T>();    vector<T> dis(N, tinf);    deque<int> q;    fora(s, S) {        dis[s] = 0;        q.push_back(s);    }    vb was(N);    while (!q.empty()) {        int f = q.front();        q.pop_front();        if (was[f])continue;        was[f] = true;        fora(e, g[f]) {            if (dis[e.t] > dis[f] + e.c) {                if (e.c) {                    dis[e.t] = dis[f] + 1;                    q.push_back(e.t);                }                else {                    dis[e.t] = dis[f];                    q.push_front(e.t);                }            }        }    }    rep(i, N)if (dis[i] == tinf)dis[i] = init_value;    return dis;}
    template<typename T> struct radixheap {    vector<pair<unsigned long long, T> > v[65];    unsigned long long size_, last;    radixheap() : size_(0), last(0) {}    bool empty() const { return size_ == 0; }    int getbit(int a) { return a ? 64 - __builtin_clzll(a) : 0; }    void emplace(unsigned long long key, const T &value) {        ++size_;        v[getbit(key ^ last)].emplace_back(key, value);    }    void push(unsigned long long key, const T &value) { emplace(key, value); }    pair<unsigned long long, T> top() {        if (v[0].empty()) {            int idx = 1;            while (v[idx].empty()) ++idx;            last = min_element(begin(v[idx]), end(v[idx]))->first;            for (auto &p : v[idx]) v[getbit(p.first ^ last)].emplace_back(p);            v[idx].clear();        }        --size_;        auto ret = v[0].back();        v[0].pop_back();        return ret;    }    void pop() { ; }    int size() { return size_; }};
//01, 密グラフ, normalを自動で判断する
    template<class Q, class T, class U,class I> vector<T> private_dijkstra(graph<T> &g, U &S_, I init_value) {    vi S = to_vi(S_);    fora(s, S) {        if (!(0 <= s && s < g.n)) {            cerr<<("dijkstra")<<endl;            deb(s, g.n);            ole();        }    }    bool cost01 = true;    rep(i, g.n) { forg_f(gi, g[i]) {forg_f_init(g[i]); cost01 &= (c == 0 || c == 1); }}    if (cost01)return dijkstra_01(g, S_, init_value); else if ((g.n + sz(g.edges)) * log2(g.n) > g.n * g.n) { return dijkstra_mitu(g, S, init_value); }    T initValue = numeric_limits<T>::max();    vector<T> dis(g.n, initValue);    Q q;    fora(s, S) {        dis[s] = 0;        q.emplace(0, s);    }    while (q.size()) {        T nowc;        int i;        tie(nowc, i) = q.top();        q.pop();        if (dis[i] != nowc)continue;        for (auto &&e  : g.g[i]) {            int to = e.t;            T c = nowc + e.c;            if (dis[to] > c) {                dis[to] = c;                q.emplace(dis[to], to);            }        }    }    /*基本、たどり着かないなら-1*/    for (auto &&d :dis) if (d == initValue)d = init_value;    return dis;}
    //O((N+M)log(N))
    template<class T, class U,class I> vector<T> dijkstra(graph<T> &g, U S_, I init_value) { if (typeid(T) == typeid(int)) { return private_dijkstra<radixheap<int>>(g, S_, init_value); } else { return private_dijkstra<priority_queue<pair<T, int>, vector<pair<T, int >>, greater<pair<T, int >> >>(g, S_, init_value); }}
//dijkstra_cou<mint> : 数える型で書く return vp(dis,cou)
    template<class COU,class T=int,class I> auto dijkstra_cou(const graph<T> &g, int s, I init_value) {    if (!(0 <= s && s < g.n)) {        cerr<<("dijkstra")<<endl;        deb(s, g.n);        ole();    }    cerr<<("count by type COU ")<<endl;    cerr<<"int or mint"<<endl;    T initValue = numeric_limits<T>::max();    vector<T> dis(g.n, initValue);    vector<COU> cou(g.n);    cou[s] = 1;    priority_queue<pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>>> q;    dis[s] = 0;    q.emplace(0, s);    while (q.size()) {        T nowc = q.top().fi;        int i = q.top().se;        q.pop();        if (dis[i] != nowc)continue;        for (auto &&e  : g.g[i]) {            int to = e.t;            T c = nowc + e.c;            if (dis[to] > c) {                dis[to] = c;                cou[to] = cou[e.f];                q.emplace(dis[to], to);            }            else if (dis[to] == c) { cou[to] += cou[e.f]; }        }    }    /*基本、たどり着かないなら-1*/    for (auto &&d :dis) if (d == initValue)d = init_value;    return vtop(dis, cou);}
//コストを無限に減らせる := -linf
//たどり着けない := linf
    template<class T> vector<T> bell(graph<T> &g, int s) {    if (g.n >= 1e4) {        cout << "bell size too big" << endl;        exit(0);    }    vector<T> res(g.n, linf);    res[s] = 0;    vb can(g.n);    /*頂点から行けない頂点を持つ、辺を消しておく */    fix([&](auto ds, int p, int i) -> void {        if (can[i])return;        can[i] = true;            forg_f(gi, g[i]){                forg_f_init(g[i]);                if (t != p)ds(i, t);            }        })(-1, 0);        vector<edge_<T>> es;        fora(e, g.edges) { if (can[e.f])es += e; }        rep(i, g.n) {            bool upd = false;            fora(e, es) {                if (res[e.f] != linf && res[e.t] > res[e.f] + e.c) {                    upd = true;                    res[e.t] = res[e.f] + e.c;                }            }            if (!upd)break;        }        rep(i, g.n * 2) {            bool upd = 0;            fora(e, g.edges) {                if (res[e.f] != linf && res[e.t] != -linf && res[e.t] > res[e.f] + e.c) {                    upd = 1;                    res[e.t] = -linf;                }            }            if (!upd)break;        }        return res;    }
//コストを無限に増やせる := linf
//たどり着けない := -linf
    template<class T> vector<T> bell_far(graph<T> &g, int s) {        if (g.n >= 1e4) {            cout << "bell_far size too big" << endl;            exit(0);        }        vector<T> res(g.n, linf);        res[s] = 0;        vb can(g.n);    /*頂点から行けない頂点を持つ、辺を消しておく*/    fix([&](auto ds, int p, int i) -> void {            if (can[i])return;            can[i] = true;            forg_f(gi, g[i]){                forg_f_init(g[i]);                if (t != p)ds(i, t);            }        })(-1, 0);        vector<edge_<T>> es;        fora(e, g.edges) { if (can[e.f])es += e; }        rep(i, g.n) {            bool upd = false;            fora(e, es) {                if (res[e.f] != linf && res[e.t] > res[e.f] - e.c) {/*-c*/                upd = true;                    res[e.t] = res[e.f] - e.c;/*-c*/            }            }            if (!upd)break;        }        rep(i, g.n * 2) {            bool upd = 0;            fora(e, g.edges) {                if (res[e.f] != linf && res[e.t] != -linf && res[e.t] > res[e.f] - e.c) {/*-c*/                upd = 1;                    res[e.t] = -linf;                }            }            if (!upd)break;        }        rep(i, g.n)res[i] *= -1;        return res;    }
//コストが負の場合も扱えたはず
    template<class T, class I> vector<vector<T>> warshall(graph<T> &g, I init_value) {    int n = g.n;    assert(n < 1e4);    vector<vector<T> > dis(n, vector<T>(n, INF<T>()));    rep(i, n)fora(e, g.g[i]) { if (dis[e.f][e.t] > e.c) { dis[e.f][e.t] = e.c; }}    rep(i, n)dis[i][i] = 0;    rep(k, n) rep(i, n) rep(j, n) { if (dis[i][j] > dis[i][k] + dis[k][j]) { dis[i][j] = dis[i][k] + dis[k][j]; }}    rep(i, n)rep(j, n) if (dis[i][j] == linf)dis[i][j] = init_value;    return dis;}
//密グラフの時、warshallに投げる
//01等の判定もここで出来る
    template<class T, class I> vector<vector<T>> dijkstra_all(graph<T> &g, I init_value) {    int n = g.n;    assert(n < 1e4);    if (n * n < (n + sz(g.edges)) * 14) {        /*O(N^3) vs O(N (N+M)log N)*/        return warshall(g, init_value); }    vector<vector<T>> dis(n);    rep(i, n) { dis[i] = dijkstra(g, i, init_value); }    return dis;}
    template<class T> class MinOp { public: T operator()(T a, T b) { return min(a, b); }};
    template<typename OpFunc> struct SparseTable {    OpFunc op;    signed size;    vector<signed> lg;    vector<vector<pair<signed, signed>>> table;    void init( vector<pair<signed, signed>> &array, OpFunc opfunc) {        signed n = array.size();        op = opfunc;        lg.assign(n + 1, 0);        for (signed i = 1; i <= n; i++) { lg[i] = 31 - __builtin_clz(i); }        table.assign(lg[n] + 1, array);        for (signed i = 1; i <= lg[n]; i++) { for (signed j = 0; j < n; j++) { if (j + (1 << (i - 1)) < n) { table[i][j] = op(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]); } else { table[i][j] = table[i - 1][j]; }}}    }    pair<signed, signed> query(signed l, signed r) {        assert(l < r);        return op(table[lg[r - l]][l], table[lg[r - l]][r - (1 << lg[r - l])]);    }};
    struct PMORMQ {    vector<signed> a;    SparseTable<MinOp<pair<signed, signed> > > sparse_table;    vector<vector<vector<signed> > > lookup_table;    vector<signed> block_type;    signed block_size, n_block;    void init( vector<signed> &array) {        a = array;        signed n = a.size();        block_size = std::max(1, (31 - __builtin_clz(n)) / 2);        while (n % block_size != 0) {            a.push_back(a.back() + 1);            n++;        }        n_block = n / block_size;        vector<pair<signed, signed> > b(n_block, make_pair(INT_MAX, INT_MAX));        for (signed i = 0; i < n; i++) { b[i / block_size] = min(b[i / block_size], make_pair(a[i], i)); }        sparse_table.init(b, MinOp<pair<signed, signed> >());        block_type.assign(n_block, 0);        for (signed i = 0; i < n_block; i++) {            signed cur = 0;            for (signed j = 0; j < block_size - 1; j++) {                signed ind = i * block_size + j;                if (a[ind] < a[ind + 1]) { cur |= 1 << j; }            }            block_type[i] = cur;        }        lookup_table.assign(1 << (block_size - 1), vector<vector<signed> >(block_size, vector<signed>(block_size + 1)));        for (signed i = 0; i < (1 << (block_size - 1)); i++) {            for (signed j = 0; j < block_size; j++) {                signed res = 0;                signed cur = 0;                signed pos = j;                for (signed k = j + 1; k <= block_size; k++) {                    lookup_table[i][j][k] = pos;                    if (i & (1 << (k - 1))) { cur++; } else { cur--; }                    if (res > cur) {                        pos = k;                        res = cur;                    }                }            }        }    }    signed query(signed l, signed r) {        assert(l < r);        signed lb = l / block_size;        signed rb = r / block_size;        if (lb == rb) { return lb * block_size + lookup_table[block_type[lb]][l % block_size][r % block_size]; }        signed pl = lb * block_size + lookup_table[block_type[lb]][l % block_size][block_size];        signed pr = rb * block_size + lookup_table[block_type[rb]][0][r % block_size];        signed pos = pl;        if (r % block_size > 0 && a[pl] > a[pr]) { pos = pr; }        if (lb + 1 == rb) { return pos; }        signed spv = sparse_table.query(lb + 1, rb).second;        if (a[pos] > a[spv]) { return spv; }        return pos;    }};

    template<class T=int> class tree : public undigraph<T> {
        PMORMQ rmq;    int cnt;    vector<signed> id_, in;    bool never = true;    bool never_hld = true;
        void dfs(int x, int p, int d, int dis = 0) {        id_[cnt] = x;        par_[x] = p;        rmq_dep.push_back(d);        disv[x] = dis;        in[x] = cnt++;        forg_f(gi, g[x]) {            forg_f_init(g[x]);            if (t == p) { continue; }            dfs(t, x, d + 1, dis + c);            id_[cnt] = x;            rmq_dep.push_back(d);            cnt++;        }    }    void precalc() {        never = false;        cnt = 0;        rmq_dep.clear();        disv.assign(n, 0);        in.assign(n, -1);        id_.assign(2 * n - 1, -1);        par_.assign(n, -1);        dfs(root, -1, 0);        rmq.init(rmq_dep);
#ifdef _DEBUG
            if (n >= 100)return;        cerr << "---tree---" << endl;        rep(i, n) {            if (!(i == root || sz(g[i]) > 1))continue;            cerr << i << " -> ";            vi ts;            forg_f(gi, g[i]) {                forg_f_init(g[i]);                if (t != par_[i])ts.push_back(t);            }            rep(i, sz(ts) - 1)cerr << ts[i] << ", ";            if (sz(ts))cerr << ts.back() << endl;        }        cerr << endl;
#endif
        }    int pos;    void hld_build() {        never_hld = false;        if (never)precalc();        g.resize(n);        vid.resize(n, -1);        head.resize(n);        heavy.resize(n, -1);        depth.resize(n);        inv.resize(n);        subl.resize(n);        subr.resize(n);        dfs(root, -1);        t = 0;        dfs_hld(root);
#ifdef _DEBUG
            if (n >= 100)return;        cerr << "---hld_index---" << endl;        vi inds;        rep(i, n) if (sz(g[i]))inds.push_back(i);        rep(i, sz(inds)) {            str s = tos(bel(inds[i]));            cerr << std::right << std::setw(sz(s) + (i ? 1 : 0)) << inds[i];        }        cerr << endl;        rep(i, sz(inds)) { cerr << bel(inds[i]) << " "; }        cerr << endl << endl;        cerr << "---hld_edge_index---" << endl;        fora(e, edges) { if (e.f <= e.t) cerr << e.f << "-" << e.t << " " << bel(e) << endl; }        cerr << endl << endl;        cerr << "!!query!! edge or not edge carefull!!" << endl;
#endif
        }    int dfs(int curr, int prev) {        int sub = 1, max_sub = 0;        heavy[curr] = -1;
            forg_f(gi, g[curr]) {            forg_f_init(g[curr]);            int next = t;            if (next != prev) {                depth[next] = depth[curr] + 1;                int sub_next = dfs(next, curr);                sub += sub_next;                if (max_sub < sub_next) max_sub = sub_next, heavy[curr] = next;            }        }        return sub;    }    int t = 0;
#ifndef __CLION_IDE__
        void dfs_hld(int v = 0) {        vid[v] = subl[v] = t;        t++;        inv[subl[v]] = v;        if (0 <= heavy[v]) {            head[heavy[v]] = head[v];            dfs_hld(heavy[v]);        }
    forg_f(gi, g[v]){forg_f_init(g[v]); if (depth[v] < depth[t])                if (t != heavy[v]) {                    head[t] = t;                    dfs_hld(t);                }        subr[v] = t;    }}
#endif//__CLION_IDE__
        vector<signed> rmq_dep;
        vi par_, depth, disv;
        vi childs;
        vi par_id_;//親への辺のidを持つ
        vvi(ids_);//隣接で辺のidを持つ
    public:
        using undigraph<T>::g;    using undigraph<T>::n;    using undigraph<T>::edges;
        int root;
        //(f,t)と(t,f)は同じidを持ち、[0,n-1]でadd順に割り振られる

        //部分木の  [左端、右端)  index
        //部分木の辺に加算する場合
        //add(subl[i],subr[i],x)
        //add(sub[i],sub[i+1],-x)
        vector<int> vid, head, heavy, inv, subl, subr;

        tree(int n_, int root = 0) : undigraph<T>(n_), root(root) { n = n_; }
        tree(int n_, int root, const vector<edge_<T>> &E) : undigraph<T>(n_), root(root) {n = n_;fora(e, E) { add(e.f, e.t, e.c); }}
        // f < t
        void add(int f, int t, T c = 1) {
#ifdef _DEBUG
            if ((n % k5) == 0) {re("tree must resize");}
#endif
            if (!(0 <= f && f < n && 0 <= t && t < n)) {            cerr<<("tree add")<<endl;            deb(f, t, c);            ole();        }
            g[f].emplace_back(f, t, c);
            g[t].emplace_back(t, f, c);
            edges.emplace_back(f, t, c);/*edgesを使わないなら消せる*/
            edges.emplace_back(t, f, c);
        }
        void add_di(int f, int t, T c = 1) {
#ifdef _DEBUG
            if ((n % k5) == 0) {            re("tree must resize");        }
#endif
            if (!(0 <= f && f < n && 0 <= t && t < n)) {            cerr<<("tree add")<<endl;            deb(f, t, c);            ole();        }        g[f].emplace_back(f, t, c);        edges.emplace_back(f, t, c);/*edgesを使わないなら消せる*/    }
        void root_change(int roo) {        root = roo;        precalc();    }
        //葉になりえない頂点を根にする
        void root_change_mid() {
#ifdef _DEBUG
    #ifdef MESSAGE
            message += "N>2 (mid)\n";
    #endif
#endif
            assert(n > 2);        rep(i, n) {            if (sz(g[i]) > 1) {                root_change(i);                return;            }        }    }
        int lca(int a, int b) {        if (never)precalc();        int x = in[a];        int y = in[b];        if (x > y) { swap(x, y); }        int pos = rmq.query(x, y + 1);        return id_[pos];    }
        int dis(int a, int b) {        if (never)precalc();        int x = in[a];        int y = in[b];        if (x > y) { swap(x, y); }        int pos = rmq.query(x, y + 1);        int p = id_[pos];        return disv[a] + disv[b] - disv[p] * 2;    }
        int dep(int a) {        if (never)precalc();        return disv[a];    }
        int par(int a) {        if (never)precalc();        return par_[a];    }
        bool isleaf(int i) {if (never)precalc();return (sz(g[i]) == 1 && i != root);}
        bool leaf(int i) { return isleaf(i); }
        //vi child(int r) {        vi res;        res.push_back(r);        queue<int> q;        q.push(r);        while (!q.empty()) {            int i = q.front();            res.push_back(i);            q.pop();            forg_f(gi, g[i]) { forg_f_init(g[i]); if (t != par(i))q.push(t); }        }        return res;    }
        vb child_ex(int r) {        vb res(n);        res[r] = true;        queue<int> q;        q.push(r);        while (!q.empty()) {            int i = q.front();            res[i] = true;            q.pop();            forg_f(gi, g[i]) {forg_f_init(g[i]); if (t != par(i))q.push(t); }        }        return res;    }
        int dfs_count_subtree(int p, int i) {        childs[i] = 1;        fort_f(gi, g[i]) {            fort_f_init(gi, g[i]);            childs[i] += dfs_count_subtree(i, t);        }        return childs[i];    }
#define count_child count_subtree
        int count_subtree(int f) {        if (sz(childs) == 0) {            if (never)precalc();            childs.resize(n);            dfs_count_subtree(-1, root);        }        return childs[f];    }
        //fからtの辺を切った時のtの大きさ
        int count_subtree(int f, int t) {        if (par(f) == t) {            return n - count_subtree(f);        } else {            return count_subtree(t);        }    }
        int size(int f, int t){return count_subtree(f, t);}
        int size(){return  n;}
        vi path(int a, int b) {        vi res;        for_each_l(a, b, [&](int i) { res.push_back(i); });        return res;    }
        //idはedgesに使えない ↓edge(id)とする
        //pathに含まれる辺のid達を返す
        vi pathe(int a,int b){
#ifdef _DEBUG
    #ifdef MESSAGE
            static bool was = 0;if(!was)message+="can't edges[id]. must edge(id)\n";was=1;
    #endif
#endif
            if(sz(par_id_)==0){            ids_.resize(n);            par_id_.resize(n);            rep(i,0,sz(edges),2){                ids_[edges[i].f].emplace_back(i>>1);                ids_[edges[i].t].emplace_back(i>>1);            }            if(never)precalc();/*par_を呼ぶため*/            rep(i, n){                int pa = par_[i];                forg_f(gi, g[i]){ forg_f_init(g[i]);                   if(t==pa){                        par_id_[i] = ids_[i][gi];                    }                }            }            }        int u = lca(a,b);        vi res;        if (a != u) {            do {                res.emplace_back(par_id_[a]);                a = par_[a];            } while (a != u);        }        vi rev;        if (b != u) {            do {                rev.emplace_back(par_id_[b]);                b = par_[b];            } while (b != u);        }        rer(i,sz(rev)-1){            res.emplace_back(rev[i]);        }        return res;
        }
        //親の辺のidを返す
        int par_id(int i){if(sz(par_id_)==0){pathe(0,0);}return par_id_[i];}
        //fのi番目の辺のidを返す
        int ids(int f,int i) {if(sz(ids_)==0){pathe(0,0);}return ids_[f][i];}
        //idから辺を返す
        edge_<T> edge(int id){return edges[id<<1];}

        /*O(N) hldを使わず木を普通にたどる liteの意*/
        void for_each_l(int u, int v, function<void(int)> fnode) {        int r = lca(u, v);        while (u != r) {            fnode(u);            u = par_[u];        }        fnode(r);        vi a;        while (v != r) {            a.push_back(v);            v = par_[v];        }        while(sz(a)){            fnode(a.back());            a.pop_back();        }    }
        void for_each_edge_l(int u, int v, function<void(edge_<int> &)> fedge) {        int r = lca(u, v);        while (u != r) {                forg_f(gi, g[u]) {forg_f_init(g[u]);                    if (t == par_[u]) {                        fedge(g[u][gi]);                        u = par_[u];                        break;                    }                }            }        vector<edge_<int>> qs;        while (v != r) {                forg_f(gi, g[v]) {  forg_f_init(g[v]);                  if (t == par_[v]) {                        qs.push_back(g[v][gi]);                        v = par_[v];                        break;                    }                }            }        while(sz(qs)){            fedge(qs.back());            qs.pop_back();        }    }
        //Fは半開 (u,v)は木の頂点
        //中ではhldの頂点を見るため、seg木のupdateはhldのindexで行なう
        void for_each_/*[l,r)*/(int u, int v, const function<void(int, int)> &f) {        if (never_hld)hld_build();        while (1) {            if (vid[u] > vid[v]) swap(u, v);            int l = max(vid[head[v]], vid[u]);            int r = vid[v] + 1;            f(l, r);            if (head[u] != head[v]) v = par_[head[v]]; else break;        }    }
        void for_each_edge/*[l,r) O(log(N)) 辺を頂点として扱っている 上と同じ感じで使える*/(int u, int v, const function<void(int, int)> &f) {        if (never_hld)hld_build();        while (1) {            if (vid[u] > vid[v]) swap(u, v);            if (head[u] != head[v]) {                int l = vid[head[v]];                int r = vid[v] + 1;                f(l, r);                v = par_[head[v]];            } else {                if (u != v) {                    int l = vid[u] + 1;                    int r = vid[v] + 1;                    f(l, r);                }                break;            }        }    }
        int bel(int v) {        /*hld内での頂点番号を返す*/        if (never_hld)hld_build();return vid[v];}
        //下の頂点に辺のクエリを持たせている
        int bel(int f, int t) {        /*辺のクエリを扱うときどの頂点に持たせればいいか(vidを返すのでそのままupd出来る)*/        if (never_hld)hld_build();return depth[f] > depth[t] ? vid[f] : vid[t];}
        int bel(edge_<T> &e) {        /*辺のクエリを扱うときどの頂点に持たせればいいか(vidを返すのでそのままupd出来る)*/        if (never_hld)hld_build();return depth[e.f] > depth[e.t] ? vid[e.f] : vid[e.t];}
        template<class ... U> int operator()(U ... args) { return bel(args...); }
        //path l -> r += v
        template<class S> void seg_add(S &seg, int lhei, int rhei, int v) {for_each_(lhei, rhei, [&](int l, int r) { seg.add(l, r, v); });}
        template<class S> void seg_update(S &seg, int lhei, int rhei, int v) {for_each_(lhei, rhei, [&](int l, int r) { seg.update(l, r, v); });}
        template<class S> T seg_get(S &seg, int lhei, int rhei) {        T res = seg.e;        for_each_(lhei, rhei, [&](int l, int r) { res = seg.f(res, seg.get(l, r)); });        return res;    }
        template<class S> void seg_add_edge(S &seg, int lhei, int rhei, int v) { for_each_edge(lhei, rhei, [&](int l, int r) { seg.add(l, r, v); }); }
        template<class S> void seg_update_edge(S &seg, int lhei, int rhei, int v) { for_each_edge(lhei, rhei, [&](int l, int r) { seg.update(l, r, v); }); }
        template<class S> T seg_get_edge(S &seg, int lhei, int rhei) {        T res = seg.e;        for_each_edge(lhei, rhei, [&](int l, int r) { res = seg.f(res, seg.get(l, r)); });        return res;    }
        //単体   edgeは上で処理できる
        template<class S> void seg_add(S &seg, int i, int v) { seg.add(bel(i), v); }
        template<class S> void seg_update(S &seg, int i, int v) { seg.update(bel(i), v); }
        template<class S> T seg_get(S &seg, int i) { return seg[i]; }
        template<class S> void seg_del(S &seg, int i) { seg.del(bel(i)); }

        //部分木iに対するクエリ
        template<class S> void seg_add_sub(S &seg, int i, int v) {if (never_hld)hld_build();seg.add(subl[i], subr[i], v);}
        template<class S> void seg_update_sub(S &seg, int i, int v) {if (never_hld)hld_build();seg.update(subl[i], subr[i], v);}
        template<class S> T seg_get_sub(S &seg, int i, int v) {if (never_hld)hld_build();return seg.get(subl[i], subr[i], v);}
        template<class S> void seg_add_sub_edge(S &seg, int i, int v) {if (never_hld)hld_build();/*iの上の辺が数えられてしまうため、i+1から*/seg.add(subl[i] + 1, subr[i], v);}
        template<class S> void seg_update_sub_edge(S &seg, int i, int v) {if (never_hld)hld_build();/*iの上の辺が数えられてしまうため、i+1から*/seg.update(subl[i] + 1, subr[i], v);}
        template<class S> T seg_get_sub_edge(S &seg, int i, int v) {if (never_hld)hld_build();/*iの上の辺が数えられてしまうため、i+1から*/return seg.get(subl[i] + 1, subr[i], v);}
    };

    //@snippet
    //グリッド上のgraph
    //grid_graph

    //区間に辺を貼れるグラフ
    //seg_graph

#define getid_2(h, w) ((h) * (W) + (w))
#define getid_1(p) ((p).first * W + (p).second)
#define o_getid(a,b,name,...) name
#define getid(...) o_getid(__VA_ARGS__, getid_2, getid_1) (__VA_ARGS__)

//forg基本

    template<class T> struct forg_edge_body {
        vector<edge_<T>> &edges;
        int i;
        explicit forg_edge_body(int i, vector<edge_<T>> &edges): i(i), edges(edges) {}
        auto operator++() {i++;}
        auto operator*() {
            return tuple<int, int, int, T>(i, edges[i].f, edges[i].t, edges[i].c);
        }
        template<class U>auto operator!=(const U& rhs){return i != rhs.i;}
    };

    template<class T> struct fort_edge_body {
        vector<edge_<T>> &edges;        int gi, ci;        int par;        void can_gi() {            while (gi < sz(edges) && edges[gi].t == par) {                gi++;            }        }        explicit fort_edge_body(int i, int par, vector<edge_<T>> &edges) : gi(i), ci(i), par(par), edges(edges) {            can_gi();        }        auto operator++() {            ci++;            gi++;            can_gi();        }
        auto operator*() {
            return tuple<int, int, int, T>(ci, edges[gi].f, edges[gi].t, edges[gi].c);
        }
        template<class U> auto operator!=(const U &rhs) { return gi != rhs.gi; }
    };
    template<class T> struct forg_edge {
        vector<edge_<T>> &edges;
        forg_edge_body<T> endp;
        forg_edge(vector<edge_<T>> &edges) : edges(edges), endp(sz(edges), edges) {}
        auto begin() { return forg_edge_body<T>(0, edges); }
        auto end() { return endp; }
    };
    template<class T> struct fort_edge {
        vector<edge_<T>> &edges;
        fort_edge_body<T> endp;
        int p;
        fort_edge(int p, vector<edge_<T>> &edges) : p(p), edges(edges), endp(sz(edges), p, edges) {}
        auto begin() { return fort_edge_body<T>(0, p, edges); }
        auto end() { return endp; }
    };
/*@formatter:off*/
/*@formatter:off*/
#define forg(gi, edges) for(auto[gi, f, t, c] :  forg_edge(edges))
#define fort(ci, edges) for(auto[ci, f, t, c] :  fort_edge(p, edges))

    template<class T> string deb_tos(digraph<T>& g){    stringstream ss;    ss<<g.n<<endl;    rep(i, g.n){        ss<<i<<" -> ";        vi ts;        forg(gi, g[i])ts += t;        rep(i, sz(ts)-1){            ss<<ts[i]<<", ";        }        if(sz(ts))ss<<ts[sz(ts)-1];        ss<<endl;    }    return ss.str();}
    template<class T> string deb_tos(undigraph<T>& g){    stringstream ss;    ss<<g.n<<endl;    rep(i, g.n){        ss<<i<<" -> ";        vi ts;        forg(gi, g[i]){            if(i <= t)ts += t;        }        rep(i, sz(ts)-1){            ss<<ts[i]<<", ";        }        if(sz(ts))ss<<ts[sz(ts)-1];        ss<<endl;    }    return ss.str();}
//@出力
    template<class T> ostream &operator<<(ostream &os, digraph<T> &g) {    os << endl << g.n << " " << sz(g.edges) << endl;    fore(gi, g.edges)    { os << f << " " << t << " " << c << endl; }    return os;}template<class T> ostream &operator<<(ostream &os, undigraph<T> &g) {    os << endl << g.n << " " << sz(g.edges) / 2 << endl;    fore(gi, g.edges){ if (f < t)os << f << " " << t << " " << c << endl; }    return os;}

#define edge edge_
//undigraphはunionfindを内蔵しているので
//same, sizeとeszieが使える
/*@formatter:on*/}

//子たちをマージしてから親に代入する
//・向いている問題
//   iを根とする部分木の数
//   子について、その部分木と空の場合のdp[child]+1通りあるため
//   (dp[child]+1)を掛けていけば良く、子だけでマージできるreroot_merge_applyが最適
////verify
//F - Distributing Integers :ABC160
//https://atcoder.jp/contests/abc160/tasks/abc160_f

//D - Driving on a Tree :square869120Contest #4
//https://atcoder.jp/contests/s8pc-4/tasks/s8pc_4_d
//G - Vertex Deletion
//ABC223 https://atcoder.jp/contests/abc223/tasks/abc223_g

// 参考
// https://null-mn.hatenablog.com/entry/2020/04/14/124151
// 辺のコストはとりあえずintのみとした
template<typename Monoid, typename EDGE, Monoid (*attract)(const Monoid &, const EDGE &), Monoid(*merge)(const Monoid &, const Monoid &), Monoid(*apply)(const Monoid &, int), Monoid(*leaf)(int), Monoid(*e_merge)()>
class reroot_merge_apply {
    int N;
    tree<int> G;
    vector<vector<Monoid>> dp;
    vector<Monoid> res;
    // dp_v = apply(merge(att(dp_c1,edge1), att(dp_c2,edge2), ..., att(dp_ck,edgek)), v)
    Monoid e;  // identity of merge
public :
    vector<Monoid> dp1;
    reroot_merge_apply() {}
    reroot_merge_apply(const tree<int> &g) : G(g), N(g.n), e(e_merge()) {
        dp.resize(N);
        for (int i = 0; i < N; ++i) dp[i].resize(G[i].size());
        dp1.resize(N);
    }
    pair<vector<Monoid>, vector<Monoid>> solve() {
        res.resize(N);
        dfs1(-1, 0);
        dfs2(-1, 0, e);
        return {dp1, res};
    }
private:

    Monoid dfs1(int p, int v) {
        Monoid res = e;
        bool update = false;
        for (int i = 0, en = G[v].size(); i < en; ++i) {
            if (G[v][i].t == p) continue;
            update = true;
            dp[v][i] = dfs1(v, G[v][i].t);
            res = merge(res, attract(dp[v][i], G[v][i]));
        }
        return dp1[v] = update ? apply(res, v) : leaf(v);
/*        return apply(res, v);*/
    }

    void dfs2(int p, int v, Monoid from_par) {
        for (int i = 0, en = G[v].size(); i < en; ++i) {
            if (G[v][i].t == p) {
                dp[v][i] = from_par;
                break;
            }
        }
        vector<Monoid> pR(G[v].size() + 1);
        pR[G[v].size()] = e;
        for (int i = G[v].size(); i > 0; --i)
            pR[i - 1] = merge(pR[i], attract(dp[v][i - 1], G[v][i - 1]));
        res[v] = apply(pR[0], v);
        Monoid pL = e;
        for (int i = 0, en = G[v].size(); i < en; ++i) {
            if (G[v][i].t != p) {
                Monoid val = merge(pL, pR[i + 1]);
                dfs2(v, G[v][i].t, en == 1 ? leaf(v) : apply(val, v));
            }
            pL = merge(pL, attract(dp[v][i], G[v][i]));
        }
    }
};
int sa, sb;//部分木のサイズを持つ

using Monoid = bool;//まとめる型
using EDGE = edge_<int>;

// dp_v = apply(merge(att(dp_c1,edge1), att(dp_c2,edge2), ..., att(dp_ck,edgek)), v)
//子の値を辺ed(f->t)で引っ張る

//例1 iを根とする部分木の個数(子の部分木の個数+1(空) を掛ければいい)
//attract = dp_v + 1
//merge   = a * b
//apply   = a

//trueなら勝ち

//マージする時の単位元
Monoid e_merge() {
    return false;
}

//子をマージできる形に変換する(辺で引っ張る(f, tでtが子))
Monoid attract_child(const Monoid &a, const EDGE &ed) {
    return a;
}

//attractの結果達をマージする
Monoid merge_child(const Monoid &a, const Monoid &b) {
    return a || b;
}

//applyはマージした結果を親に代入する時の処理
Monoid apply_root(const Monoid &a, int node) {
    return !a;
}

Monoid leaf(int node) {
    return true;
}

/*@formatter:off*/
pair<Monoid, signed> e_cou() { return pair<Monoid, signed>(e_merge(), 0); }
pair<Monoid, signed> attract_cou(const pair<Monoid, signed> &a, const EDGE &ed) {return pair<Monoid, signed>(attract_child(a.first, ed), a.second);}
pair<Monoid, signed> merge_cou(const pair<Monoid, signed> &a, const pair<Monoid, signed> &b) {sa = a.second;sb = b.second;return pair<Monoid, signed>(merge_child(a.first, b.first), a.second + b.second);}
pair<Monoid, signed> apply_cou(const pair<Monoid, signed> &a, int node) { return pair<Monoid, signed>(apply_root(a.first, node), a.second + 1);/*根(自分)をマージする操作なので+1*/}
pair<Monoid, signed> leaf_cou(int node) {return pair<Monoid, signed>(leaf(node), 1);/*根(自分)をマージする操作なので+1*/}


pair<vector<Monoid>, vector<Monoid>> reroot(const tree<int> &g) {reroot_merge_apply<Monoid, EDGE, attract_child, merge_child, apply_root, leaf, e_merge> rero(g);return rero.solve();}

//部分木のサイズにsa, sbでアクセス出来る
pair<vector<Monoid>, vector<Monoid>> reroot_size(const tree<int> &g) {reroot_merge_apply<pair<Monoid, signed>, EDGE, attract_cou, merge_cou, apply_cou, leaf_cou, e_cou> rero(g);auto[dp1, dp2] = rero.solve();vector<Monoid> res1;/*deb*/vector<Monoid> res2;for (auto&[k, v] : dp1) { res1.emplace_back(k); }for (auto&[k, v] : dp2) { res2.emplace_back(k); }return {res1, res2};}
/*@formatter:on*/


//親をサイズ1のnodeとして、そこに子をマージしていく
//・向いている問題
// 白と黒で黒が隣り合ってはいけない塗り分け系等
//reroot_apply_merge

//デバッグのため、1回目のdpも返す
//auto[dp1, res] = reroot(g);


signed main() {
    int N;
    cin >> N;
    tree<> g(N);
    g.ing(N, N - 1);
    auto[dp1, ret] = reroot(g);

    deb(dp1);
    deb(ret);
 /*   rep(i, N){
        cout << i<<"dp"<<dp1[i] << endl;
    }
    rep(i, N){
        cout << i<<" ret "<<ret[i] << endl;
    }*/
    int cou = 0;
    for (auto r : ret) {
        if (r)cou++;
    }
    cout << cou << endl;
    rep(i, N) {
        if (ret[i]) {
            cout << (i + 1) << endl;
        }
    }
    return 0;
}