P4350 [CERC2015] Export Estimate

Luka owns a geographic data company that maintains a detailed city map and exports the data to interested parties. Often, clients do not want the complete map. Instead, they want a simplified map containing only major streets.

#### 题意翻译： Luka 拥有一个地理数据公司保持着详细的城市地图和出口相关的数据。但是通常客户不想要完整的地图。相反，他们更想要一个只包含主要街道的简单地图： 1. 所有优先级小于 $p$ 的街道被删除 1. 对于每一个路口点 $i$ 从 $1$ 到 $n$（按照这个顺序处理）： (a)如果这个路口没有连接到任何街道，它就会被删除。 (b)如果路口 $i$ 正好连接到两个不同的街道 $x$ 和 $y$，导致 $a$ 和 $b$ 两个路口都与路口 $i$ 不同，那么 $i$ 就会根据下面的过程进行收缩： i.删除道路 $x$ 和道路 $y$； ii.删除路口 $i$； iii.加入一个连接路口 $a$ 和 $b$ 的新道路 $z$； 最初，图中没有环（即一条连接到自身的边）或者平行的边（即在同一对交点之间有一条以上的边），但在收缩的过程中可能会形成环和平行边。 请注意，在步骤2.（b）之前，$x$ 和 $y$ 都不能是环（即 $a$ 和 $b$ 必须和 $i$ 不同），但是新增的 $z$ 可以是一个环（即 $a$ 和 $b$ 可能是相同的）。 给定一个地图和一系列的出口的询问,每个询问找到路口的数量和街道地图出口的数量。

无

无

Central Europe Regional Contest 2015 Problem E