哥萨克胡子最近来到了一个非常有趣的国家。该国有 个城市，其中编号为 的城市是国家的 首都。这些城市之间恰好有 条道路，第 条道路连接城市 和 。同时已知，从任何一个城市都可以通过仅在这些道路上移动而到达任何其他城市。
每个城市都是某个区域的中心。区域 被定义为所有顶点 的集合，使得从首都到 的任何路径都必须经过该区域的中心（一个城市可以属于多个区域）。
编号为 的城市恰好居住着 位公民，并且所有 的值 互不相同。胡子得知，国家政府有权执行 “人口交换” 操作——选择一对城市 和 ，并将城市 的 所有 居民迁往城市 ，同时将城市 的 所有 居民迁往城市 。我们的哥萨克最多可以请求政府执行 次 “人口交换”。进行 “人口交换” 时所选的城市对也由胡子指定。
每天，哥萨克都会选择一个数字作为他当天的“最喜欢的数字”。如果 是胡子最喜欢的数字，那么他认为一个区域是 “优美区域”，当且仅当可以通过不超过 次 “人口交换” 操作，使得该区域内各城市人口数量的 中位数 等于 。也就是说，如果将区域内城市的人口数量按 升序 排列，那么所得序列中间位置的元素值（即 中位数）必须等于 。如果区域内的城市数量是偶数，那么中间两个元素中，靠右（即数值较大）的那个元素的值必须等于 。例如，集合 的 中位数 是 ，而集合 的 中位数 是 。
哥萨克将在这个国家再逗留恰好 天。每天早晨他会告知他最喜欢的数字，而你需要告诉他 “优美区域” 的数量。
