Oh! I was not aware that it’s secret.
I tried with PYPY but with the same result. Still no idea what else I can improve 
# https://www.spoj.com/problems/AKBAR/
# This improved version of bsf with multiple sources
import sys
from collections import deque
class Graph:
def __init__(self, n):
self.adj = [[] for _ in range(n)]
self.n = n
def bfs(g: Graph):
# variable initialization
protected_by = [None for _ in range(g.n)]
power_left = [None for _ in range(g.n)]
# setup sources (soldiers)
list_of_sources = [i for i in range(g.n) if g.soldiers[i] is not None]
non_zero_sources = [i for i in range(g.n) if g.soldiers[i] is not None and g.soldiers[i] > 0]
for i in list_of_sources:
power_left[i] = g.soldiers[i]
protected_by[i] = i
q = deque(non_zero_sources)
# Main loop
while len(q) != 0:
u = q[0]
for v in g.adj[u]:
if protected_by[v] is not None and protected_by[v] != protected_by[u]:
return -1
if protected_by[v] is None:
protected_by[v] = protected_by[u]
power_left[v] = power_left[u] - 1
if power_left[v] > 0:
q.append(v)
q.popleft()
if None in protected_by:
return -1
def verify(g: Graph):
result = bfs(g)
if result == -1:
print("No")
else:
print("Yes")
def main():
with sys.stdin as f:
# with open("input") as f:
t = int(f.readline())
for test_case in range(t):
# print(f" === Test case {test_case} ===")
n, r, m = ([int(i) for i in f.readline().split()]) # cities, roads, soldiers
g = Graph(n)
g.soldiers = [None for _ in range(n)]
for road in range(r):
a, b = ([int(i) - 1 for i in f.readline().split()])
g.adj[a].append(b)
g.adj[b].append(a)
for soldier in range(m):
city, strength = ([int(i) for i in f.readline().split()])
g.soldiers[city - 1] = strength
verify(g)
if __name__ == '__main__':
main()
