八中有 个房间和 双向通道，任意两个房间均可到达. 现在出了一件极 BT 的事，就是八中开始闹鬼了。老大决定加强安保，现在如果在某个房间中放一个士兵，则这个房间以及所有与这个房间相连的房间都会被控制. 现在老大想 知道至少要多少士兵可以控制所有房间. 以及有多少种不同的方案数.
第一行一个数字 代表有 个房间，房间编号从 开始到 。下面将有 行，每行两个数，代表这两个房间相连。
第一行输出至少有多少个士兵才可以控制所有房间第二行输出有多少种方案数，方案数会比较大，输出除以 的余数吧.
6 1 2 1 3 1 5 1 4 5 6
2 2
第一种方案是将士兵放在 号房间及 号房间 第二种方案是将士兵放在 号房间及 号房间
对于 的数据，。
