#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; //using namespace atcoder; #define REP(i, n) for (int i=0; i<(n); ++i) #define RREP(i, n) for (int i=(int)(n)-1; i>=0; --i) #define FOR(i, a, n) for (int i=(a); i<(n); ++i) #define RFOR(i, a, n) for (int i=(int)(n)-1; i>=(a); --i) #define SZ(x) ((int)(x).size()) #define ALL(x) (x).begin(),(x).end() #define DUMP(x) cerr<<#x<<" = "<<(x)< ostream &operator<<(ostream &os, const vector &v) { os << "["; REP(i, SZ(v)) { if (i) os << ", "; os << v[i]; } return os << "]"; } template ostream &operator<<(ostream &os, const pair &p) { return os << "(" << p.first << " " << p.second << ")"; } template bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; } template bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; } using ll = long long; using ull = unsigned long long; using ld = long double; using P = pair; using vi = vector; using vll = vector; using vvi = vector; using vvll = vector; const ll MOD = 1e9 + 7; const int INF = INT_MAX / 2; const ll LINF = LLONG_MAX / 2; const ld eps = 1e-9; // edit template, typename F2=function> struct Rerooting { struct Edge { int to; int rev; O w; }; vector> graph; vector> dp; vector> vis; const int N; const E ie; // 要素の単位元 const F1 f1; const F2 f2; Rerooting(int N, E ie, F1 f1, F2 f2) : graph(N), dp(N), vis(N), N(N), ie(ie), f1(f1), f2(f2) { } // 重みとかがない場合でもwに適当な値を入れておくこと void add_edge(int u, int v, O w) { int su = graph[u].size(); int sv = graph[v].size(); graph[u].push_back({v, sv, w}); graph[v].push_back({u, su, w}); } // 根をrとしたときrのc番目の子の値を求める E dfs_sub(int r, int c) { if (vis[r][c]) return dp[r][c]; vis[r][c] = true; E &ret = dp[r][c]; int u = graph[r][c].to; int su = graph[u].size(); // TODO //葉に対する例外処理  if (graph[u].size() == 1) { ret = 1; return ret; } bool win_exist = false; for (int i = 0; i < su; ++i) { int v = graph[u][i].to; if (v == r) continue; E sub_res = dfs_sub(u, i); // TODO // ret = f2(ret, f1(sub_res, graph[u][i].w)); if (sub_res) { win_exist = true; } } // TODO 問題によってはここで処理が生じる // 例: TDPC-V ret = !win_exist; return ret; } void dfs_all(int u, int p = -1) { int su = graph[u].size(); vector es(su + 2, 0); vector lce(su + 2, 0); vector rce(su + 2, 0); for (int i = 0; i < su; ++i) { // TODO es[i + 1] = lce[i + 1] = rce[i + 1] = dfs_sub(u, i); } for (int i = 0; i <= su; ++i) { // lce[i + 1] = f2(lce[i], lce[i + 1]); lce[i + 1] = lce[i] || lce[i + 1]; } for (int i = su + 1; i > 0; --i) { // rce[i - 1] = f2(rce[i], rce[i - 1]); rce[i - 1] = rce[i] || rce[i - 1]; } for (int i = 0; i < su; ++i) { // vが根のときのuに関する値を求める int v = graph[u][i].to; int rev = graph[u][i].rev; vis[v][rev] = true; // TODO // uが葉の場合の例外処理 if (graph[u].size() == 1) { dp[v][rev] = 1; continue; } // TODO // dp[v][rev] = f2(lce[i], rce[i + 2]); dp[v][rev] = !(lce[i] || rce[i + 2]); } for (int i = 0; i < su; ++i) { int v = graph[u][i].to; if (v == p) continue; dfs_all(v, u); } } vector build(int root = 0) { // dp, visの初期化 for (int i = 0; i < N; ++i) { dp[i].resize(graph[i].size(), ie); vis[i].resize(graph[i].size(), false); } dfs_all(root, -1); vector ret(N, ie); for (int u = 0; u < N; ++u) { int su = graph[u].size(); bool win_exist = false; for (int i = 0; i < su; ++i) { // 部分問題を求める E sub_res = dfs_sub(u, i); // TODO // 部分問題の結果に作用素を作用させる // E applied_res = f1(sub_res, graph[u][i].w); // TODO // ret[u] = f2(ret[u], applied_res); if (sub_res) win_exist = true; } ret[u] = !win_exist; } return ret; } }; void solve() { int N; cin >> N; using E = int; using O = int; E ie = -1; using F1 = function; using F2 = function; F1 f1 = [](E e, O o) -> void { }; F2 f2 = [](E e1, E e2) -> void { }; Rerooting rr(N + 1, ie, f1, f2); REP(i, N - 1) { int a, b; cin >> a >> b; rr.add_edge(a, b, 0); } auto res = rr.build(1); vector win_node; FOR(i, 1, N + 1) { if (res[i]) { win_node.push_back(i); } } cout << win_node.size() << endl; for (auto node: win_node) { cout << node << endl; } } int main() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(10); // std::ifstream in("input.txt"); // std::cin.rdbuf(in.rdbuf()); solve(); return 0; }