#3176. 交换美食

交换美食

题目描述

新的一年,又是一场美食秀,作为吃货的小 P 也来参加了。

其中一个节目是“交换美食”。节目是这样的:大厨会制作 nn 道菜,而小 P 最喜欢的是第 kk 道菜。做完菜后,大厨会娴熟的进行一些交换操作,一共 mm 次,每次会将放在第 uiu_i 个位置和第 viv_i 个位置的菜交换。为了吃到小 P 喜欢的那道菜,也就是让那道菜最终停在小 P 所在的第 jj 个位置,小 P 可以让大厨取消几次交换操作,但是这样会打断大厨娴熟的操作,因此会让菜凉掉。所以,小 P 需要让取消的次数尽可能的少,但是小 P 的脑子不太好使,于是小 P 来求助你。

输入格式

第一行三个整数 n,m,kn,m,k,表示菜的种类数,总操作次数和小 P 最喜欢的那道菜的初始位置。

下面 mm 行,每行两个整数 ui,viu_i,v_i,表示这次操作选择的两个位置。

输出格式

共一行 nn 个整数,第 ii 个整数表示是小 P 最喜欢的那道菜停在第 ii 个位置上的最少取消次数。

若不可能停在该位置,则输出 1-1

样例 #1

样例输入 #1

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

样例输出 #1

2 0 3 1 -1

提示

测试点编号 nn mm
11 20\le20 =0=0
22 20\le20
343\sim4 103\le10^3
565\sim6 103\le10^3
787\sim8 104\le10^4
9109\sim10 105\le10^5