在一个王国里有 个城市,城市之间通过魔法传送门相连。
每对不同的城市之间有且仅有一个魔法传送门,允许从一个城市瞬间移动到另一个城市。
由于魔法传送门的特殊性质,每个传送门只能单向使用。对于每对城市 和 ,已知是否可以使用传送门从 到 或从 到 。
由于魔法传送门的特殊性,王国居民从一个城市到另一个城市时,有时需要使用多个传送门。此外,可能存在某些城市对之间不能通过任何魔法传送门到达。
王国的居民称一个城市为“完美城市”,如果可以仅使用魔法传送门从该城市到达王国的所有其他城市。假设初始时王国中有个完美城市。
最近国王决定选择一对城市,并将连接它们的传送门的方向反转。为了选择最佳方案,国王希望了解,通过调整一个传送门,王国中的完美城市数量可能发生的变化。
报告中包含对于每个整数 ,使得 ,满足以下条件的城市对 的数量:
- 原始魔法传送门允许从城市 直接移动到城市 ;
- 如果将此魔法传送门的移动方向反转,使其允许从城市 直接移动到城市 ,则王国中完美城市的数量将变为 。
因此,部分报告仅包含那些通过调整传送门方向严格增加完美城市数量的方案。完整报告包含所有通过调整一个传送门的方向所得到的情况。
为了获取这些信息,国王计划向交通部请求相应的报告。国王可以请求部分报告或完整报告。报告的内容取决于参数 ,对于部分报告,,对于完整报告,。
任务:编写一个程序,根据给定的魔法传送门方向信息生成相应的报告。