U611922 比较

给定无向图 $G= \left( V, E \right)$，其中 $V=\left\{ 1, 2, \ldots , n \right\}$，以及函数 $p: V \to V$ 和 $f: V \to V$，保证 $\left\{p\left( i \right) |\ i \in V \right\} = V$。对于 $G$ 的任意路径 $P$ 和 $v \in V$，记 $C\left( P, v \right)$ 为 $P$ 中 $f$ 值为 $v$ 的结点数，即 $C\left( P, v \right) = \sum_{u \in V\left( P \right)} \left[ f\left( u \right) = v \right]$，其中 $V\left( P \right)$ 为路径 $P$ 经过的点集（包括起点和终点）。对于两条路径 $P_1$ 和 $P_2$，$P_1$ 和 $P_2$ 的比较方法如下：取最小的 $i$，满足 $C\left( P_1, p\left( i \right) \right) \ne C\left( P_2, p\left( i \right) \right)$，则定义 $C\left( P_j, p\left( i \right) \right)$ 较大的那条路径 $P_j$ 较大。若所有的 $C\left( P_1, p\left( i \right) \right) = C\left( P_2, p\left( i \right) \right)$，则认为 $P_1$ 和 $P_2$一样大。请你求出以 $1$ 为起点，$n$ 为终点的所有路径中最小的一条。

第一行两个正整数 $n$ 和 $m$，其中 $n=\left| V \right|$，$m=\left| E \right|$。 第二行 $n$ 个整数，第 $i$ 个数为 $p\left( i \right)$. 第三行 $n$ 个整数，第 $i$ 个数为 $f\left( i \right)$. 接下来 $m$ 行每行两个整数 $u, v$，给出所有的无向边。

共一行，对于所求的最小路径，依次输出 $C\left( P, p\left( 1 \right) \right)$ 个 $p\left( 1 \right),C\left( P, p\left( 2 \right) \right)$ 个 $p\left( 2 \right),\dots,C\left( P, p\left( n \right) \right)$ 个 $p\left( n \right)$. 保证存在最小的路径。

对 $20\%$ 的数据，$n\le 10,m\le 50$. 对于 $50\%$ 的数据，$n\le 5000,m\le 5000$. 对于 $100\%$ 的数据，$n\le 100000,m\le 500000$.