Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:512 MB
统计

1.1 题目描述
动物园里有 n 只动物,每只动物都属于 s 个物种之一,可以用 [1, s] 范围内的整数描述。
对于任意两个物种,它们之间要么是友好的,要么会发生冲突。共有 l 对物种之间是友好关 系,会在输入中给出。
现在 n 只动物排成了一行,第 i 只动物属于 ai 号物种。你想把它们重新排列,但要遵循以下 原则:
(1). 可以操作任意多次,但每次只能交换相邻两只动物。
(2). 对于交换的两只动物,它们所属的物种之间必须是友好关系。
最终,你想让动物序列的字典序尽量小。也就是说,先最小化排在第一位的动物所属的种族, 再考虑排在第二位的动物,以此类推。
1.2 输入输出格式
1.2.1 输入格式
第一行,三个整数 s, l, n。
接下来 l 行,每行两个整数 ai , bi,表示这两个物种是友好关系。
下一行,n 个整数 c1, c2, ... , cn,表示初始的动物序列。
1.2.2 输出格式
一行,n 个整数,表示通过交换能得到的最优的动物序列。
1.3 样例
1.3.1 样例输入

3 2 6
2 3
1 2
1 3 3 2 3 1
1.3.2 样例输出

1 2 3 3 3 1
1.4 限制
对于 25% 的数据,n ≤ 200。
对于 50% 的数据,n ≤ 3000。
对于另外 25% 的数据,s ≤ 10。
对于 100% 的数据,$1 ≤ s ≤ 200, 1 ≤ n ≤ 10^5$。
保证 $ai \neq bi$,且对于任意 $i \neq j$,集合$ {ai , bi} \neq {aj , bj}$。