题干:

The country Treeland consists of n cities, some pairs of them are connected with unidirectional roads. Overall there are n - 1 roads in the country. We know that if we don't take the direction of the roads into consideration, we can get from any city to any other one.

The council of the elders has recently decided to choose the capital of Treeland. Of course it should be a city of this country. The council is supposed to meet in the capital and regularly move from the capital to other cities (at this stage nobody is thinking about getting back to the capital from these cities). For that reason if city a is chosen a capital, then all roads must be oriented so that if we move along them, we can get from city a to any other city. For that some roads may have to be inversed.

Help the elders to choose the capital so that they have to inverse the minimum number of roads in the country.

Input

The first input line contains integer n (2 ≤ n ≤ 2·105) — the number of cities in Treeland. Next n - 1 lines contain the descriptions of the roads, one road per line. A road is described by a pair of integers si, ti (1 ≤ si, ti ≤ nsi ≠ ti) — the numbers of cities, connected by that road. The i-th road is oriented from city si to city ti. You can consider cities in Treeland indexed from 1 to n.

Output

In the first line print the minimum number of roads to be inversed if the capital is chosen optimally. In the second line print all possible ways to choose the capital — a sequence of indexes of cities in the increasing order.

Examples

Input

3
2 1
2 3

Output

0
2 

Input

4
1 4
2 4
3 4

Output

2
1 2 3 

题目大意:

 给出N个点,其中有N-1条有向边,边的方向可以改变,问最少改变多少条边可以从某一个点到达任意一个点,同时求出这些点。

解题报告:

给一段一句话题解:

要改变的边的权值为1,不需要改变的边的权值为0,两次dfs,第一次算出以1点为根节点到所有点要改变的边数,第二次以1为根节点向下遍历节点
 3 算出每一个点到达所有点要改变的边数,dp[son]+=(dp[root]-dp[son])+((tree[i].val)?-1:1),某一点的值是他父节点
 4 的值减去他以前的值再考虑他与父节点之间的边的方向。

  其实就是两边dfs就好了,第一遍是正常的递归以cur为根的状态值,第二遍求出转移到cur的那一半的状态值。也就是第一次dfs是用儿子更新父亲,第二次dfs是用父亲处理一下之后来更新儿子。好题啊精妙的!!

AC代码:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX = 2e5 + 5;
int n;
int a,b;
ll dp[MAX];//指向我的有多少条边 
ll ans[MAX];
struct Node {
	int to;
	bool f;//1==实边,0==虚边 
	Node(){}
	Node(int to,int f):to(to),f(f){}
};
vector<Node> vv[MAX];
void dfs(int cur,int root) {
	int up = vv[cur].size();
	for(int i = 0; i<up; i++) {
		Node v = vv[cur][i];
		if(v.to == root) continue;
		dfs(v.to,cur);
		dp[cur] += dp[v.to];
		if(v.f == 0) dp[cur]++; 
	}
}
void DFS(int cur,int root) {
	int up = vv[cur].size();
	for(int i = 0; i<up; i++) {
		Node v = vv[cur][i];
		if(v.to == root) continue;
		dp[v.to] += (dp[cur]-dp[v.to]);
		if(v.f) dp[v.to]++;
		else dp[v.to]--;
		DFS(v.to,cur);
	}
}
int main()
{
	cin>>n;
	for(int i = 1; i<=n-1; i++) {
		scanf("%d%d",&a,&b);
		vv[a].pb(Node(b,1));vv[b].pb(Node(a,0));
	}
	dfs(1,-1);
	DFS(1,-1);
	ll minn = 0x3f3f3f3f3f;
	for(int i = 1; i<=n; i++) minn = min(minn,dp[i]);
	printf("%lld\n",minn);
	int ans = 0;
	for(int i = 1; i<=n; i++) {
		if(minn == dp[i]) printf("%d ",i);
	}
	return 0 ;
 }

总结: 代码中DFS中无意间调用了dfs,TLE8了,,但是没有wa,,仔细想一下确实是不会wa的,,这里的dp不会再重新算一遍,因为叶子结点的dp永远没有改变过,所以不会出现多调用一次dfs就会使每个节点dp的值成倍的增加的现象。所以其实在这里多调用一次dfs顶多算是重新求了一次dp的值,并不会使dp改变成原来的多少倍那样、、

注意DFS的更新顺序,,不然就会出错!!总之牢牢把握住,更新状态的前提是所用的值一定是所需的完成值就好了。