Description

在无向的校园里，有n个地点和m条边，柳予欣有两个女朋友fyx,lmz分别住在地点1和n。

请问柳予欣分别在1-n这几个地点的时候，三个人想要凑在一起约会的最短的（三人分别到约会地点的最短路径之和）是多少？（柳予欣住在每个地点时，约会地点都可以重新任选）

Format

Input

第一行两个数$n,m$。$(0\leq n\leq 1e5,0\leq m\leq 1e5)$

下面m行分别两个数a,b表示地点a,b间有一条路径长为1。(保证为一个连通图)

Output

输出一行一共n个数，第i-th数表示柳予欣在地点i的时候，三个人约会在一起的最短路径和是多少。

Samples

4 3
1 2
2 3
2 4

2 2 3 2