CF1339D Edge Weight Assignment

You have unweighted tree of n vertices. You have to assign a positive weight to each edge so that the following condition would hold:

  • For every two different leaves v1 and v2 of this tree, bitwise XOR of weights of all edges on the simple path between v1 and v2 has to be equal to 0.

Note that you can put very large positive integers (like $10^{10}$).

It’s guaranteed that such assignment always exists under given constraints. Now let’s define f as the number of distinct weights in assignment.

img

In this example, assignment is valid, because bitwise XOR of all edge weights between every pair of leaves is 0. ff value is 2 here, because there are 2 distinct edge weights(4 and 5).

img

In this example, assignment is invalid, because bitwise XOR of all edge weights between vertex 1 and vertex 6 (3,4,5,4) is not 0.

What are the minimum and the maximum possible values of f for the given tree? Find and print both.

Input

The first line contains integer n ($3≤n≤10^5$) — the number of vertices in given tree.

The ii-th of the next n−1 lines contains two integers ai and bi ($1≤ai<bi≤n$) — it means there is an edge between ai and bi. It is guaranteed that given graph forms tree of n vertices.

Output

Print two integers — the minimum and maximum possible value of f can be made from valid assignment of given tree. Note that it’s always possible to make an assignment under given constraints.

Examples

input

1
2
3
4
5
6
6
1 3
2 3
3 4
4 5
5 6

output

1
1 4

input

1
2
3
4
5
6
6
1 3
2 3
3 4
4 5
4 6

output

1
3 3

首先找到一个度为 1 的点作为树根构造树。记录每个节点的深度 d[i] 和其到其最深的叶子节点的距离 l[i]

可以观察到：

对于可分配的最大值有

1、一个父亲节点的所有 $l[i] = 1$ 的子节点一共可以分配一个值（因为之前的路径上的值是已经分配好的，要想 XOR 为 0, 这里必须分配同一个值），其他的可以各自分配一个。有一个例外就是 当 $d[i] <= 3$ 因为到根节点的距离 = 2，所以不分配新的值。

对于可分配的最小值有

1、如果根到某一个叶子节点的边数为偶数，则分配一个值足以。

2、如果为奇数，则最多需要三个。简单证明：$x = 3 + x’$ , $x 为奇数x’ 为偶数$ 偶数分配一个值，三个奇数需要三个值，总的下来需要三个值。

所以可以这样判断，对于所有不为根的叶子节点如果有奇数，则可分配的最小值为 3，否则 为1。2 的话显然可以用 1 替换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
const int MAX=100000+10;
int n,a,b,sz[MAX],rt=0,vis[MAX],l[MAX],d[MAX],_min=1,_max=0;
struct edge{
	int to,next;
}e[MAX*2];
int head[MAX],tot=0;
void addedge(int u,int v){
	e[tot].to = v;
	e[tot].next = head[u];
	head[u] = tot++;
} 
int dfs(int u){
	vis[u]=1;
	int cnt=0;
	for(int i=head[u];i!=-1;i=e[i].next){
		int v = e[i].to;
		if(vis[v]) continue;
		cnt++;
		d[v] = d[u]+1;
		l[u] = max(l[u],dfs(v));
	}
	if(cnt==0) return l[u]=0;
	else return ++l[u];
}
void dfs2(int u){
	vis[u]=1;
	int zo = 1;
	for(int i=head[u];i!=-1;i=e[i].next){
		int v = e[i].to;
		if(vis[v]) continue;
		if(l[v] == 0){
			if(zo && d[v]>3){
				zo = 0;
				_max ++;
			}
		}else if(l[v]>0) _max++;
		dfs2(v);
	}
}
int main(){
//	freopen("in","r",stdin);
	mem(head,-1);mem(sz,0);mem(vis,0);mem(l,0);
	sf(n);
	fi(i,0,n-1){
		sf(a);sf(b);
		addedge(a,b);addedge(b,a);
		sz[a]++;sz[b]++;
	}
	fi(i,1,n+1)
		if(sz[i]==1) {
			rt = i; break;
		}
	d[rt] = 1;
	dfs(rt);
	fi(i,1,n+1)
		if(sz[i] == 1 && i != rt && (d[i]-1) & 1){
			_min = 3; break;
		}
	mem(vis,0);
	dfs2(rt);
	pf(_min);pfc(" ");pfn(_max);
	return 0;
}