2314 - 士兵的放置

八中有N个房间和N-1双向通道,任意两个房间均可到达.现在出了一件极BT的事,就是八中开始闹鬼了。老大决定加强安保，现在如果在某个房间中放一个士兵,则这个房间以及所有与这个房间相连的房间都会被控制.现在 老大想知道至少要多少士兵可以控制所有房间.以及有多少种不同的方案数.

Input

第一行一个数字N,代表有N个房间,房间编号从1开始到N.N<=500000,下面将有N-1行,每行两个数,代表这两个房间相连.

Output

第一行输出至少有多少个士兵才可以控制所有房间第二行输出有多少种方案数,方案数会比较大,输出除以1032992941的余数吧.

Examples

Input

6
1 2
1 3
1 5
1 4
5 6

Output

2
2

Hint

第一种方案是将士兵放在1号房间及6号房间

第二种方案是将士兵放在1号房间及5号房间

Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题