剪贴板 lzgw6peh

### 题目描述 你有一棵 $n$ 个点的有根树，点 $i$ 上写有一个数字 $a_i$，保证 $\{a_i\}$ 构成一个 $1\sim n$ 的排列。你想要将 $a_i$ 重排，使得最终点 $i$ 上的数字恰好是 $i$。 你可以进行如下操作：依次遍历 $i=1,2,\cdots,n$，选择一个 $i$ 的子树中的点 $j$（$i,j$ 可以相同），交换 $a_i$ 与 $a_j$ 的值。 你需要判断是否有解，如果有解请构造一种方案。 **根可以不为 $1$，不保证一个结点的父亲编号小于它。** 多组数据，$n\le 2\times 10^5,\sum n\le 5\times 10^5$。