그래프에서 임의의 두 정점 사이의 거리(Distance)는 두 정점 사이의 최단 경로에 포함된 간선의 개수이다. BFS(breadth-first search, 너비 우선 탐색)를 사용하면 임의의 정점에서 나머지 모든 정점까지의 최단 거리를 구할 수 있다.

dist[x] = 1번 정점에서 x번 정점까지의 거리 배열을 유지하면서 위 그래프의 1번 정점에서 BFS를 시작해보자. dist[1] = 0으로 초기화한다.

dist[2] = dist[1] + 1, dist[4] = dist[1] + 1을 기록한다.

dist[3] = dist[2] + 1, dist[5] = dist[2] + 1을 기록한다.

dist[6] = dist[3] + 1을 기록한다. 그래프의 모든 정점까지의 거리를 저장하는 배열 dist가 완성되었다.

주어진 그래프의 1번 정점을 기준으로 나머지 모든 정점까지의 거리를 구해보자. 1번 정점에서 1번 정점까지 거리는 0이다.

입력

첫째 줄에 그래프의 정점의 개수와 간선의 개수 ~N, M(1 \le N, M \le 50)~이 주어진다. 그래프의 각 정점에는 1부터 N까지 번호가 매겨져 있다.

둘째 줄부터 M개의 줄에 그래프의 간선이 주어진다. 간선은 서로 다른 두 정점 ~u, v(1 \le u, v \le N)~를 잇는다. 주어지는 그래프는 단순 그래프(Simple graph)이다. 따라서 두 정점을 잇는 간선은 최대 한 개 존재할 수 있으며, 자기 자신을 잇는 간선은 없다.

또한 주어지는 그래프는 연결 그래프(Connected graph)이다. 따라서 1번 정점에서 BFS를 통해 모든 정점을 방문할 수 있다.

출력

주어진 그래프의 1번 정점에서 나머지 모든 정점까지의 거리를 출력한다.

예제 입력 1

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

예제 출력 1

0 1 2 1 2 3

힌트

BFS 과정 중에 유지하는 visit 배열 외에 거리를 따로 저장하는 dist 배열을 정의한 후에 채워줍니다.