!/bin/python3

import math import os import random import re import sys from collections import defaultdict

This class represents a directed graph

using adjacency list representation

class Graph:

# Constructor
def __init__(self):

    # Default dictionary to store graph
    self.graph = defaultdict(list)

# Function to add an edge to graph
def addEdge(self, u, v):
    self.graph[u].append(v)

# Function to print a BFS of graph
def BFS(self, s):
    dico = dict()
    # Mark all the vertices as not visited
    visited = [False] * (max(self.graph) + 1)
    # Create a queue for BFS
    queue = []
    queue0 = []
    # Mark the source node as
    # visited and enqueue it
    if (s not in self.graph):
        print(-1)
        dico[s]=-1
        return dico
    queue.append(s)
    queue0.append(0)
    visited[s] = True
    cmpt=1
    l=[0]
    k=0
    dico = dict()
    while queue:

        # Dequeue a vertex from
        # queue and print it
        s = queue.pop(0)
        print(s,end=" ")
        #s0=queue0.pop(0)
        print(l[k]*cmpt)
        dico[s]=l[k]*cmpt
        k+=1



        # Get all adjacent vertices of the
        # dequeued vertex s.
        # If an adjacent has not been visited,
        # then mark it visited and enqueue it
        maxp=max(l)
        for i in self.graph[s]:
            if visited[i] == False:
                l.append(maxp+1)
                queue.append(i)
                visited[i] = True
    return dico

Complete the findShortest function below.

#

For the weighted graph, :

#

1. The number of nodes is _nodes.

2. The number of edges is _edges.

3. An edge exists between _from[i] to _to[i].

# # def findShortest(graph_nodes, graph_from, graph_to, ids, val): # solve here n= graph_nodes g = Graph() for i in range(len(graph_from)): g.addEdge(graph_from[i],graph_to[i]) g.addEdge(graph_to[i],graph_from[i]) if ids.count(val)<=1: return -1 dico = g.BFS(val) for i in range(1,n+1): if i not in dico.keys(): dico[i]=g.BFS(i)[i] s=[] for k in range(len(ids)): if ids[k]==2 and dico[k+1]>0: s.append(dico[k+1]) print(s)

return min(s)

if name == 'main': fptr = open(os.environ['OUTPUT_PATH'], 'w')

graph_nodes, graph_edges = map(int, input().split())

graph_from = [0] * graph_edges
graph_to = [0] * graph_edges

for i in range(graph_edges):
    graph_from[i], graph_to[i] = map(int, input().split())

ids = list(map(int, input().rstrip().split()))

val = int(input())

ans = findShortest(graph_nodes, graph_from, graph_to, ids, val)

fptr.write(str(ans) + '\n')

fptr.close()