提示: 欢迎访问OurACM平台。
Problem 1697 Contest of Bike

Accept: 90    Submit: 425
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

今年福州大学将举办100年一届的“福州大学自行车比赛”,所有的大学城的学生都很积极的参加了这场盛况空前的比赛。
ccQ和Cxw都很关注这场比赛,他们决定派一个人到现场实时报道比赛情况,由于参加比赛的人很多,因此现场很乱,谁也不想跑去让自行车撞,于是他们用dotA决定谁该去。然而Cxw的“月之女神”被ccQ的“风暴精灵”给打暴了,可怜的Cxw只好到现场走一趟了。
cxw越想越不对,输的有点诡异,他开始怀疑ccQ是不是作弊了。于是Cxw决定捉弄一下ccQ。

Input

每组数据的第一行n和m(2<= n,m<= 10000),表示有n个人参加了比赛和m条cxw发回的信息,接下来n个数xi(1<= i<= n),xi表示运动员的标号以及比赛开始时是排在第i个。 再接下来有m对数xa和xb(xa!=xb,1<= xa,xb<= n),表示编号为xa的运动员刚好超过编号为xb的运动员。Cxw想捉弄ccQ,所以他有时故意交换xa和xb的数值。

Output

每组数据输出一行,表示比赛的最后排名情况。

Sample Input

5 5 1 2 3 4 5 1 2 3 4 1 2 3 4 5 1 5 5 1 2 3 4 5 1 2 3 4 5 1 1 2 3 4

Sample Output

5 1 2 3 4 1 2 5 3 4

Source

FOJ-2009年4月月赛 CCQ

Submit  Back  Status  Discuss