JOI 국은 \(N\)개의 마을과 이를 잇는 \(M\)개의 길로 이루어져 있다. 마을에는 1부터 \(N\)까지, 길에는 1부터 \(M\)까지 번호가 붙어 있다. 길 \(i\) (\(1 \le i \le M\))는 마을 \(A_i\)와 마을 \(B_i\)를 양방향으로 잇는다. \(A_i < B_i\)이며, 두 마을 사이를 잇는 길은 많아야 1개이다. 즉 \(A_i \ne A_j\) 또는 \(B_i \ne B_j\) (\(1 \le i < j \le M\))이다.

비타로는 현재 마을 \(s\)에 있으며, 여행 계획을 세우고 있다. 여행 계획은 비타로가 방문할 마을 번호의 순서를 나타내는 수열 \(v = (v_1, v_2, \ldots)\)로 표현한다. \(v\)는 1 이상 \(N\) 이하의 정수로 이루어진 길이 1 이상의 수열이다. 비타로는 방문 순서에 까다로운 조건이 있어, \(v\)의 길이를 \(l\)이라 할 때 다음을 모두 만족해야 한다.

• \(v_1 = s\)
• 각 \(j = 1, 2, \ldots, l - 1\)에 대해, 마을 \(v_j\)와 마을 \(v_{j+1}\)은 길로 연결되어 있다.
• 각 \(j = 1, 2, \ldots, l - 1\)에 대해, \(j\)가 홀수이면 \(v_j < v_{j+1}\), \(j\)가 짝수이면 \(v_j > v_{j+1}\)이 성립한다.

예를 들어 \(v = (2)\)나 \(v = (1, 4, 1, 5, 3)\)은 세 번째 조건을 만족하지만, \(v = (3, 2)\)는 세 번째 조건을 만족하지 않는다.

비타로는 어떤 여행 계획을 세워도 도달할 수 없는 마을, 즉 위 조건을 모두 만족하는 어떤 수열 \(v\)에도 나타나지 않는 마을이 모두 몇 개인지 궁금해 한다.

현재 비타로가 어느 마을에 있는지는 모르므로, \(s = 1, 2, \ldots, N\) 각각에 대해 비타로의 질문에 대한 답을 구하라.

JOI 국의 마을과 길에 대한 정보가 주어졌을 때, \(s = 1, 2, \ldots, N\) 각각에 대해, 어떤 여행 계획을 세워도 도달할 수 없는 마을의 개수를 구하는 프로그램을 작성하라.