Problem: We have an undirected graph G with N vertices numbered 1 to N and N edges as follows:    * For each i=1,2,...,N-1, there is an edge between Vertex i and Vertex i+1.   * There is an edge between Vertex X and Vertex Y.  For each k=1,2,...,N-1, solve the problem below:    * Find the number of pairs of integers (i,j) (1 \leq i < j \leq N) such that the shortest distance between Vertex i and Vertex j in G is k.

Submission attempts (in order):
import queue
from collections import deque
import numpy as np
n, x, y = map(int,input().split())
g = [[] for _ in range(n)] 
for i in range(n-1):

    g[i] += i+1,
    g[i+1] += i,
g[x-1] += y-1,
g[y-1] += x-1,

# if n%2==0:
#     ma = int(n/2)
# else:
#     ma = int((n+1)/2)
# print(ma)

ans = [0]*n
for start in range(n):
    dist = [-1] * n
    dist[start] = 0
    
    
    q = deque([start])
    while q:
        
        v = q.popleft()
        for nv in g[v]:
            if dist[nv] == -1:
                dist[nv] = dist[v]+1
                
                q.append(nv)
    for i in dist:
        ans[i] += 1
    
# d = np.array(d).flatten()


#     print(int(ans[i]/2))
print(' '.join(str(i//2) for i in ans[1:]))


import queue
from collections import deque
import numpy as np
n, x, y = map(int,input().split())
g = [[] for _ in range(n)] 
for i in range(n-1):

    g[i] += i+1,
    g[i+1] += i,
g[x-1] += y-1,
g[y-1] += x-1,

# if n%2==0:
#     ma = int(n/2)
# else:
#     ma = int((n+1)/2)
# print(ma)

ans = [0]*n
for i in range(n):
    start = i
    dist = [-1] * n
    dist[start] = 0
    
    
    q = deque([start])
    while q:
        
        v = q.popleft()
        for nv in g[v]:
            if dist[nv] == -1:
                dist[nv] = dist[v]+1
                
                q.append(nv)
    for i in dist:
        ans[i] += 1
    
# d = np.array(d).flatten()


#     print(int(ans[i]/2))
print(' '.join(str(i//2) for i in ans[1:]))


import queue
from collections import deque
import numpy as np
n, x, y = map(int,input().split())
g = [[] for _ in range(n)] 
for i in range(n-1):

    g[i].append(i+1)
    g[i+1].append(i)
g[x-1].append(y-1)
g[y-1].append(x-1)

# if n%2==0:
#     ma = int(n/2)
# else:
#     ma = int((n+1)/2)
# print(ma)

ans = [0]*n
for i in range(n):
    start = i
    dist = [-1] * n
    dist[start] = 0
    
    
    q = deque([start])
    while q:
        
        v = q.popleft()
        for nv in g[v]:
            if dist[nv] == -1:
                dist[nv] = dist[v]+1
                
                q.append(nv)
    for i in dist:
        ans[i] += 1
    
# d = np.array(d).flatten()


#     print(int(ans[i]/2))
print(' '.join(str(i//2) for i in ans[1:]))


import queue
from collections import deque
import numpy as np
n, x, y = map(int,input().split())
g = [[] for _ in range(n)] 
for i in range(n-1):

    g[i] += i+1,
    g[i+1] += i,
g[x-1] += y-1,
g[y-1] += x-1,

# if n%2==0:
#     ma = int(n/2)
# else:
#     ma = int((n+1)/2)
# print(ma)

ans = [0]*n
for start in range(n):
    dist = [-1] * n
    dist[start] = 0
    
    
    q = deque([start])
    add,pop = q.append,q.popleft
    while q:
        
        v = pop()
        for nv in g[v]:
            if dist[nv] == -1:
                dist[nv] = dist[v]+1
                
                add(nv)
    for i in dist:
        ans[i] += 1
    
# d = np.array(d).flatten()


#     print(int(ans[i]/2))
print(' '.join(str(i//2) for i in ans[1:]))


from collections import deque
n, x, y = map(int,input().split())
g = [[] for _ in range(n)] 
for i in range(n-1):

    g[i] += i+1,
    g[i+1] += i,
g[x-1] += y-1,
g[y-1] += x-1,
a = [0]*n
for start in range(n):
    d = [-1] * n
    d[start] = 0
    q = deque([start])
    add,pop = q.append,q.popleft
    while q:
        v = pop()
        for nv in g[v]:
            if d[nv] < 0:
                d[nv] = d[v]+1
                add(nv)
    for i in d:
        a[i] += 1
print(' '.join(str(i//2) for i in a[1:]))


import queue
from collections import deque
import numpy as np
n, x, y = map(int,input().split())
g = [[] for _ in range(n)] 
for i in range(n-1):

    g[i] += i+1,
    g[i+1] += i,
g[x-1] += y-1,
g[y-1] += x-1,
a = [0]*n
for start in range(n):
    d = [-1] * n
    d[start] = 0
    
    
    q = deque([start])
    add,pop = q.append,q.popleft
    while q:
        
        v = pop()
        for nv in g[v]:
            if d[nv] < 0:
                d[nv] = d[v]+1
                
                add(nv)
    for i in d:
        a[i] += 1
    
# d = np.array(d).flatten()


#     print(int(ans[i]/2))
print(' '.join(str(i//2) for i in a[1:]))


def main():
    dist = []
    import numpy as np
    from collections import deque
    n, x, y = map(int,input().split())
    g = [[] for _ in range(n)] 
    for i in range(n-1):

        g[i] += i+1,
        g[i+1] += i,
    g[x-1] += y-1,
    g[y-1] += x-1,
    a = [0]*n
    for start in range(n):
        d = [-1] * n
        d[start] = 0
        q = deque([start])
        add,pop=q.append,q.popleft
        while q:
            v = pop()
            for nv in g[v]:
                if d[nv] < 0:
                    d[nv] = d[v]+1
                    add(nv)
        
        #     a[i] += 1
        dist.extend(d)
    for i in dist:
        a[i] += 1
    # dist = np.array(dist).flatten()
    
    #     print(int(len([x for x in dist if x==i])/2))
    for i in range(1,n):
        print(int(a[i]/2))
main()

Verdicts: Time Limit Exceeded

Time Limit Exceeded

Time Limit Exceeded

Time Limit Exceeded

Time Limit Exceeded

Time Limit Exceeded

Accepted