#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 struct Rerooting { struct Edge { int to; int rev; O w; }; vector> graph; vector> dp; vector> vis; const int N; Rerooting(int N) : graph(N), dp(N), vis(N), N(N) { } // 重みとかがない場合でも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 = true; return ret; } // TODO 探索前の処理 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 sub_resに辺(u,v)を適用 // E applied_res = f1(sub_res, graph[u][i].w) // TODO // ret = f2(ret, applied_res); win_exist = win_exist || sub_res; } // TODO 探索後の処理 // 例: TDPC-V ret = !win_exist; return ret; } void dfs_all(int u, int p = -1) { int su = graph[u].size(); // TODO 初期値を定めておく vector es(su + 2, 0); vector lce(su + 2, 0); vector rce(su + 2, 0); for (int i = 0; i < su; ++i) { E sub_res = dfs_sub(u, i); // TODO sub_resに辺(u, v)を適用し、es lce rceに代入 // es[i + 1] = lce[i + 1] = rce[i + 1] = f1(sub_res, graph[u][i].w); es[i + 1] = lce[i + 1] = rce[i + 1] = sub_res; } 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()); vis[i].resize(graph[i].size(), false); } dfs_all(root, -1); vector ret(N); // uの子の結果を利用してuの値を求める for (int u = 0; u < N; ++u) { int su = graph[u].size(); // TODO 探索前の処理 bool win_exist = false; for (int i = 0; i < su; ++i) { // 部分問題を求める E sub_res = dfs_sub(u, i); // TODO sub_resに辺(u,v)を適用 // E applied_res = f1(sub_res, graph[u][i].w); // TODO // ret[u] = f2(ret[u], applied_res); win_exist = win_exist || sub_res; } // TODO 探索後の処理 ret[u] = !win_exist; } return ret; } }; void solve() { int N; cin >> N; Rerooting rr(N+1); REP(i, N - 1) { int a, b; cin >> a >> b; rr.add_edge(a, b, 0); } auto res = rr.build(1); vector anss; FOR(i, 1, N + 1) { if (res[i]) anss.push_back(i); } cout << anss.size() << endl; for (auto ans: anss) { cout << ans << 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; }