#P18227. Guide Map
Guide Map
Guide Map
Byteland 有 座城市,任意两座不同城市之间都有一条双向道路。其中恰有 条道路沿途有景观。保证只要适当地再选择一条道路建设景观,就能仅沿有景观的道路从任意城市到达其他所有城市。换句话说,现有的有景观道路构成两棵树,其中一棵可以只有一个顶点。
Little Q 最初位于城市 ,手里拿着一份只标有部分道路的导游地图。他按照下面的规则旅行。假设当前位于城市 :
- 如果地图上有一条从 通往尚未访问过的城市的道路,他会选择这些城市中编号最小的一个 ,并沿这条道路走到 。城市 在旅行开始时就算已经访问。
- 否则,他会沿着第一次进入城市 时所走的道路返回。如果此时已经位于城市 ,则旅行立即结束。
Little Q 希望沿途经过所有有景观的道路,同时经过的不同无景观道路不超过一条。
求有多少份不同的导游地图能够满足他的要求。每份地图可以是全部道路集合的任意子集;当且仅当某条道路出现在其中一份地图而没有出现在另一份地图时,这两份地图不同。
答案对 取模。
注意,限制的是旅行时实际经过的不同无景观道路数,不是地图上标出的无景观道路数。沿原路返回不增加不同道路的种类。也不要求访问每座城市,只要求经过全部景观。
输入格式
本题只有一个测试用例。
第一行包含一个整数 ,表示城市数。
接下来 行,每行包含两个整数 ,表示城市 之间的道路有景观。
数据范围:
保证有景观道路满足题目中给出的条件。
输出格式
输出一个整数,表示满足要求的导游地图数量对 取模的结果。
样例 1
4
1 4
2 3
6
样例 2
2
2
样例说明
第一组样例中,一份可行地图标有 四条道路。Little Q 的旅行过程为
他经过了两条有景观道路,而实际经过的无景观道路只有 ;虽然地图还标出了无景观道路 ,他没有沿它行走。
第二组样例中没有有景观的道路。地图可以标出唯一的道路 ,也可以不标出它,两种都满足要求。