题解

思路

连通图有 $N$ 个顶点和 $N$ 条边，因此图中恰好有一个环。删除环上的边后，每个连通块恰好包含一个环上顶点，并是一棵以该环点为根的树。

若两个顶点位于同一棵这样的树中，它们之间只有树上的唯一简单路径。若它们属于不同的环点，则可以沿环的两个方向连接这两个环点，因此存在两条简单路径。问题等价于判断两个顶点所归属的环上根是否相同。

做法

维护每个顶点的度数，把所有度数为 $1$ 的顶点加入队列并反复删除。删除过程结束后，未被删除的顶点恰好是唯一环上的顶点。

令每个环上顶点的根为它自己。再从所有环点同时出发，只沿非环边遍历，把挂在该环点上的整棵树标成相同的根。每次询问只需比较两个顶点的根。

对于 $Q\le20$ 的子任务，也可以对每次询问在图中枚举简单路径，并在找到两条时停止。由于图中只有一个环，任意两点之间至多有两条简单路径。

若所有非环点都是叶子，那么度数为 $1$ 的顶点就是非环点，其唯一邻点就是所属环点；其他顶点都是环点，可以直接由度数完成分类。

证明

不断删除叶子不会删除环上的顶点，并最终会删除所有挂在环上的树，因此剩余顶点恰为唯一环。

同一环根的两个顶点之间的路径完全位于一棵树中，所以唯一。不同环根之间必须经过环；环上两个不同顶点之间沿顺时针和逆时针各有一条简单路径，接上两端各自树中的唯一路径后得到两条不同的简单路径。因此比较环根与题目答案完全等价。

复杂度

剥叶、标记根和回答询问均为线性过程，总时间复杂度为 $O(N+Q)$，空间复杂度为 $O(N)$。