当前没有测试数据。

题目描述

某局域网中有 $N$ 台电脑，编号为 $1 \sim N$。电脑之间通过网络线缆连接，共有 $M$ 条连接线缆，每条线缆连接两台电脑，使得这两台电脑之间可以互相传输数据。

不幸的是，其中一台电脑感染了病毒。病毒可以通过网络线缆传播到其他电脑。每经过一条线缆，病毒传播的时间为 $1$ 个单位时间。也就是说，如果病毒从电脑 $A$ 传播到电脑 $B$，经过的路径长度为 $L$，则需要 $L$ 个单位时间。

现在，已知病毒最初出现在编号为 $S$ 的电脑上，请计算出病毒传播到每台电脑所需的最短时间。如果某台电脑无法被传播到，输出 $-1$。

输入格式

第 $1$ 行读入 $3$ 个整数 $N, M, S$。

接下来 $M$ 行，每行 $2$ 个整数 $U, V$，表示电脑 $U$ 和电脑 $V$ 之间有一条线缆连接。

输出格式

输出一行 $N$ 个整数，第 $i$ 个整数表示病毒传播到电脑 $i$ 的最短时间。

样例

输入

4 4 1
1 2
2 3
3 4
1 4

输出

0 1 2 1

数据范围

对于 $100\%$ 的数据，满足 $1 \le N \le 10^5$，$1 \le M \le 2 \times 10^5$，$1 \le S \le N$。