题目描述

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

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

输入格式

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

下面 $m$ 行，每行两个整数 $u_i,v_i$，表示这次操作选择的两个位置。

输出格式

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

若不可能停在该位置，则输出 $-1$。

样例 #1

样例输入 #1

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

样例输出 #1

2 0 3 1 -1

提示