该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

这是 $CSP-J$ 模拟赛的 $T2$ 。

题目描述

桌子上有 $n$ 颗糖果排成一行，但是第 $k$ 颗糖果坏了。

你的老师给你 $m$ 次要求，这些要求需要按给定顺序执行，第 $i$ 次要求你将第 $u_i$ 和 $v_i$ 颗糖果交换，这样坏的糖果就可能会被交换到一个新的位置。

但由于你希望进行暗箱操作，你可以拒绝执行其中的若干条要求，使得坏的糖果最终交换到 $p$ 号位置。

由于骗过老师很累，请对于每个 $p \in [1,n]$ 求出最少可能的不执行要求条数，使得坏的糖果在第 $p$ 个位置。

输入格式

输入多行。

第一行三个整数 $n,m,k$ ，表示糖果个数，总操作次数和坏糖果的初始位置。

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

输出格式

输出一行。

共一行 $n$ 个整数，第 $i$ 个整数表示使坏糖果最终停留在该位置所需的最少暗箱操作次数。

若最终坏糖果不可能停留在该位置 $i$ 则输出 $-1$ 。

样例 #1

样例输入 #1

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

样例输出 #1

2 0 3 1 -1

提示

数据范围】：

对于 $20\%$ 的数据，满足 $n \le 10 , m=0$ 。

对于另外 $40\%$ 的数据，满足 $n \le 10^3 , m \le 10^3$ 。

对于另外 $20\%$ 的数据，满足 $n \le 10^3 , m \le 10^5$ 。

对于 $100\%$ 的数据，满足 $1 \le n \le 10^5 , 1 \le m \le 10^5 , 1 \le k \le n$ 。