Problem:


パケット転送

インターネットでは、データはパケットに分割され、パケットごとにルータと呼ばれる中継機器を介して宛先に転送されます。各ルータはパケットに記載された宛先から次に転送すべきルータを判断します。さらに、無限にルータ間を転送され続けることを防ぐため、パケットには TTL（Time To Live） という値が付加されています。ルータは受け取ったパケットの TTL を 1 減算し、その結果が 0 ならそのパケットを破棄し、それ以外なら次のルータに転送します。

そこで、ネットワークの設計を手助けするプログラムを作ることになりました。ネットワークの接続情報と送信パケットの情報を入力として、各パケットが宛先ルータに到着するまでに経由するルータの数のうち最小の値を表示するプログラムを作成してください。

ネットワークは図のように複数のルータとそれらを結ぶケーブルで構成されています。ただし、各接続（ケーブル）は単方向であることに注意してください。各ルータが直接つながっているルータの番号の配列がネットワークの接続の情報として与えられます。ルータの数を n とすれば、各ルータは 1 から n までの整数で識別されます。送信元から宛先ルータまでの経路が複数ある場合は、経由するルータの数が少ない方の値を出力してください。また、パケットが宛先に到達しない場合は NA と出力してください。

例えば、以下の図のようなネットワークで、送信元ルータが 6、宛先ルータが 5 の場合を考えます。最短経路は 6→1→5 であり経由するルータは 3 個です。この場合、TTL はルータ 6、1 でそれぞれ減算されるので、送信時の TTL が 3 以上であればパケットは到達できます。宛先ルータでは TTL を減算する必要はありません。また、送信元と宛先が同じルータになるようなパケットは無いものとします。

Input

入力は以下の形式で与えられます。

n
r1 k1 t11 t12 ... t1k1
r2 k2 t21 t22 ... t2k2
:
rn kn tn1 tn2 ... tnkn
p
s1 d1 v1
s2 d2 v2
:
sp dp vp

1 行目にルータの総数 n（n ≤ 100）、続く n 行に i 番目のルータの接続情報が与えられます。接続情報として、i 番目のルータの番号 ri、i 番目のルータと直接接続しているルータの個数 ki、i 番目のルータから送信できるルータの番号 ti1, ti2, ... tikiが与えられます。

続く行にパケットの個数 p（p ≤ 1000）、続く p 行に i 番目のパケットの情報が与えられます。パケットの情報として、 送信元ルータの番号 si, 宛先ルータの番号 di, TTL の値 vi (0 ≤ vi ≤ 10000) が与えられます。

Output

各パケットごとに、経由するルータの個数または NA を１行に出力してください。

Sample Input

7
1 4 2 5 4 3
2 1 5
3 1 6
4 1 7
5 2 7 6
6 1 1
7 0
6
1 2 2
1 5 3
1 2 1
5 1 3
6 3 3
1 7 4

Output for the Sample Input

2
2
NA
3
3
3



Sample input:
7
1 4 2 5 4 3
2 1 5
3 1 6
4 1 7
5 2 7 6
6 1 1
7 0
6
1 2 2
1 5 3
1 2 1
5 1 3
6 3 3
1 7 4


Sample output:
2
2
NA
3
3
3

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
rlst = [None] * (n + 1)
#print(rlst)
for _ in range(n):
  lst = list(map(int, input().split()))
  r = lst[0]
  print(r)
  lst = lst[2:]
  rlst[r] = lst

p = int(input())

for _ in range(p):
  s, d, v = map(int, input().split())
  visited = [False] * (n + 1)
  visited[s] = True
  que = deque()
  que.append((s, 1))
  while que:
    node, dist = que.pop()
    if node == d:
      print(dist)
      break
    if dist < v:
      for to in rlst[node]:
        if not visited[to]:
          que.append((to, dist + 1))
  else:
    print("NA")

Submission status: Wrong Answer

Solution code:
from collections import deque

n = int(input())
rlst = [None] * (n + 1)
for _ in range(n):
  lst = list(map(int, input().split()))
  r = lst[0]
  lst = lst[2:]
  rlst[r] = lst

p = int(input())

for _ in range(p):
  s, d, v = map(int, input().split())
  visited = [False] * (n + 1)
  visited[s] = True
  que = deque()
  que.append((s, 1))
  while que:
    node, dist = que.pop()
    if node == d:
      print(dist)
      break
    if dist < v:
      for to in rlst[node]:
        if not visited[to]:
          que.append((to, dist + 1))
  else:
    print("NA")

Submission status: Wrong Answer

Solution code:
from collections import deque

n = int(input())
rlst = [None] * (n + 1)
for _ in range(n):
  lst = list(map(int, input().split()))
  r = lst[0]
  lst = lst[2:]
  rlst[r] = lst

p = int(input())

for _ in range(p):
  s, d, v = map(int, input().split())
  visited = [False] * (n + 1)
  visited[s] = True
  que = deque()
  que.append((s, 0))
  while que:
    node, dist = que.pop()
    if node == d:
      print(dist + 1)
      break
    if dist < v - 1:
      for to in rlst[node]:
        if not visited[to]:
          que.append((to, dist + 1))
  else:
    print("NA")

Submission status: Wrong Answer

Solution code:
from collections import deque

n = int(input())
rlst = [None] * (n + 1)
for _ in range(n):
  lst = list(map(int, input().split()))
  r = lst[0]
  lst = lst[2:]
  rlst[r] = lst

p = int(input())

for _ in range(p):
  s, d, v = map(int, input().split())
  visited = [False] * (n + 1)
  visited[s] = True
  que = deque()
  que.append((s, 0))
  while que:
    node, dist = que.pop()
    if node == d:
      print(dist + 1)
      break
    if dist < v - 1:
      for to in rlst[node]:
        if not visited[to]:
          que.append((to, dist + 1))
          visited[to] = True
  else:
    print("NA")

Submission status: Wrong Answer

Solution code:
from collections import deque

n = int(input())
rlst = [None] * (n + 1)
for _ in range(n):
  lst = list(map(int, input().split()))
  r = lst[0]
  lst = lst[2:]
  rlst[r] = lst

p = int(input())

for _ in range(p):
  s, d, v = map(int, input().split())
  visited = [False] * (n + 1)
  visited[s] = True
  que = deque()
  que.append((s, 0))
  while que:
    node, dist = que.pop()
    if node == d:
      if dist < v:
        print(dist + 1)
      else:
        print("NA")
      break
    for to in rlst[node]:
      if not visited[to]:
        que.append((to, dist + 1))
        visited[to] = True
  else:
    print("NA")

Submission status: Time Limit Exceeded

Solution code:
def f1(r, g, ttl, c, res):
    global max_c
    c += 1
    if r == g:
        max_c = c
        return True
    ttl -= 1
    if ttl == 0:
        return
    elif max_c is not None and c >= max_c-1:
        return
    elif r in res:
        return
    else:
        res.append(r)
        for r in dic[r]:
            if f1(r, g, ttl, c, res[:]):
                return

dic = {}
for i in range(input()):
    line = map(int, raw_input().split())
    dic[line[0]] = line[2:]

for i in range(input()):
    s, g, ttl = map(int, raw_input().split())
    max_c = None
    f1(s, g, ttl, 0, [])
    if max_c:
        print max_c
    else:
        print 'NA'

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n=input()
r=[map(int,raw_input().split()) for _ in xrange(n)]
m=input()
pa=[map(int,raw_input().split()) for _ in xrange(m)]
for i in xrange(m):
    d=[1]*n
    q=deque([pa[i][0]])
    used=[False]*n
    used[pa[i][0]-1]=True
    while len(q)!=0:
        f=0
        p=q.popleft()
        p-=1
        if d[p]==pa[i][2]:continue
        for j in r[p][2:]:
            j-=1
            if pa[i][1]-1==j:
                f=1
                d[j]+=d[p]
                break
            if used[r[j][0]-1]:continue
            q.append(j+1)
            d[j]=d[p]+1
            used[j]=True
        if f==1:
            break
    if f==1:
        print(d[j])
    else:
        print("NA")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n=int(raw_input())
r=[map(int,raw_input().split()) for _ in xrange(n)]
m=int(raw_input())
pa=[map(int,raw_input().split()) for _ in xrange(m)]
for i in xrange(m):
    d=[1]*n
    q=deque([pa[i][0]])
    used=[False]*n
    used[pa[i][0]-1]=True
    while len(q)!=0:
        f=0
        p=q.popleft()
        p-=1
        if d[p]==pa[i][2]:break
        for j in r[p][2:]:
            j-=1
            if pa[i][1]-1==j:
                f=1
                d[j]+=d[p]
                break
            if used[r[j][0]-1]:continue
            q.append(j+1)
            d[j]=d[p]+1
            used[j]=True
        if f==1:
            break
    if f==1:
        print(d[j])
    else:
        print("NA")

Submission status: Memory Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0144

"""
import sys
from sys import stdin
input = stdin.readline
from enum import Enum


class Graph(object):
    """ single source shortest path """
    class Status(Enum):
        """ ?????????????¨??????¶??? """
        white = 1  # ????¨????
        gray = 2  # ?¨???????
        black = 3  #?¨???????

    def __init__(self, n, data):
        num_of_nodes = n+1
        self.color = [Graph.Status.white] * num_of_nodes  # ????????????????¨??????¶???
        self.M = [[float('inf')] * num_of_nodes for _ in range(num_of_nodes)]
        self._make_matrix(data)  # data????????????????????£??\??????(?????\?¶???¨???????????????????????§????????????)
        self.d = [float('inf')] * num_of_nodes  # ?§???????????????????(?????????)
        self.p = [-1] * num_of_nodes  # ????????????????????????????¨?????????????????????????

    def _make_matrix(self, data):
        for d in data:
            r = d[0]
            for t in d[2:]:
                self.M[r][t] = 1

    def dijkstra(self, start):
        self.d[start] = 0
        self.p[start] = -1
        while True:
            mincost = float('inf')
            # ??\??????????????§??????????????¨?????????????????????u???????????????
            for i in range(len(self.d)):
                if self.color[i] != Graph.Status.black and self.d[i] < mincost:  # S????±???????????????????S??¨??\?¶?????????????????????????????????????????°???????????????????
                    mincost = self.d[i]
                    u = i  # u??????????????????ID
            if mincost == float('inf'):
                break
            self.color[u] = Graph.Status.black  # ?????????u???S????±???????????????´???
            for v in range(len(self.d)):
                if self.color[v] != Graph.Status.black and self.M[u][v] != float('inf'):
                    # v????????????????????????????????°??????S???????????£???u????????????????????????????????????????????°??????????????±??§??´??°??????
                    if self.d[u] + self.M[u][v] < self.d[v]:
                        self.d[v] = self.d[u] + self.M[u][v]
                        self.p[v] = u
                        self.color[v] = Graph.Status.gray


def main(args):
    n = int(input())
    network = []
    for _ in range(n):
        network.append([int(x) for x in input().split()])

    packets = []
    p = int(input())
    for _ in range(p):
        packets.append([int(x) for x in input().split()])

    for s, d, v in packets:
        g = Graph(n, network)
        g.dijkstra(s)
        path = [d]
        u = d
        while g.p[u] != s:
            path.append(g.p[u])
            u = g.p[u]
        path.append(s)

        if len(path) > v:
            print('NA')
        else:
            print(len(path))



if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
inf = 2**31

n = int(raw_input())
G = [[inf]*n for _ in range(n)]
ref = {}
inputs = [map(int,raw_input().split()) for _ in range(n)]
for i in range(n): ref[inputs[i][0]] = i
for i in range(n):
    for j in inputs[i][2:]:
        G[i][ref[j]] = 1
        
for k in range(n):
    for i in range(n):
        for j in range(n):
            G[i][j] = min(G[i][j],G[i][k]+G[k][j])
            
p = int(raw_input())
for loop in range(p):
    s,d,v = map(int,raw_input().split())
    dist = G[ref[s]][ref[d]]
    print dist+1 if dist+1 <= v else "NA"

Submission status: Accepted

Solution code:
def solve(A):
  s,d,v = A
  C = [-1 for _ in [0]*(n+1)]
  c = 1
  C[s] = c
  SP = M[s]
  while 1:
    if SP==[]: return "NA"
    c += 1
    X = []
    for p in SP:
      if C[p]>0: continue
      C[p] = c
      for e in M[p]:
        if C[e]<0 and e not in SP: X.append(e)
      if p==d:
        if C[p]>v: return "NA"
        else: return C[p]
    SP = X

n = int(raw_input())
M = {}

for _ in [0]*n:
  x = map(int, raw_input().split())
  M[x[0]]=x[2:]
for _ in [0]*int(raw_input()):
  print solve(map(int,raw_input().split()))

Submission status: Accepted

Solution code:
def solve(A):
  s,d,v = A
  C = [-1 for _ in [0]*(n+1)]
  c = 1
  C[s] = c
  SP = M[s]
  while 1:
    if SP==[]: return "NA"
    c += 1
    X = []
    for p in SP:
      if C[p]>0: continue
      C[p] = c
      X += [e for e in M[p] if C[e]<0 and e not in SP]
      if p==d: return [C[d],"NA"][C[p]>v]
    SP = X

n = int(raw_input())
M = {}

for _ in [0]*n:
  x = map(int, raw_input().split())
  M[x[0]] = x[2:]
for _ in [0]*int(raw_input()):
  print solve(map(int,raw_input().split()))

Submission status: Accepted

Solution code:
n=int(raw_input())
g=[[1000000]*n for _ in xrange(n)]
for i in xrange(n):
    g[i][i]=0
for i in xrange(n):
    r=map(int,raw_input().split())
    for j in r[2:]:
        g[r[0]-1][j-1]=1
for k in xrange(n):
    for i in xrange(n):
        for j in xrange(n):
            g[i][j]=min(g[i][j],g[i][k]+g[k][j])
m=int(raw_input())
for i in xrange(m):
    s,d,v=map(int,raw_input().split())
    s-=1
    d-=1
    if g[s][d]<v:
        print(g[s][d]+1)
    else:
        print('NA')

Submission status: Accepted

Solution code:
n = input()
E0 = {}
V = set()
for i in xrange(n):
    ipt = map(int, raw_input().split())
    r = ipt[0]; k = ipt[1]; T = ipt[2:]
    E0[r] = T
    V.add(r)
E = {v: {} for v in V}
for v in V:
    for t in E0[v]:
        E[v][t] = 1
MAX = 10**18
for k in V:
    for i in V:
        for j in V:
            if k in E[i] and j in E[k]:
                E[i][j] = min(E[i].get(j, MAX), E[i][k] + E[k][j])
p = input()
for i in xrange(p):
    s, d, v = map(int, raw_input().split())
    print "NA"*(v <= E[s].get(d, MAX))or E[s][d]+1

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0144

"""
import sys
from sys import stdin
input = stdin.readline
from enum import Enum


class Graph(object):
    """ single source shortest path """
    class Status(Enum):
        """ ?????????????¨??????¶??? """
        white = 1  # ????¨????
        gray = 2  # ?¨???????
        black = 3  #?¨???????

    def __init__(self, n, data):
        num_of_nodes = n+1
        self.color = [Graph.Status.white] * num_of_nodes  # ????????????????¨??????¶???
        self.M = [[float('inf')] * num_of_nodes for _ in range(num_of_nodes)]
        for i in range(num_of_nodes):
            self.M[i][i] = 0
        self._make_matrix(data)  # data????????????????????£??\??????(?????\?¶???¨???????????????????????§????????????)
        self.d = [float('inf')] * num_of_nodes  # ?§???????????????????(?????????)
        self.p = [-1] * num_of_nodes  # ????????????????????????????¨?????????????????????????

    def _make_matrix(self, data):
        for d in data:
            r = d[0]
            for t in d[2:]:
                self.M[r][t] = 1

    def dijkstra(self, start):
        self.d[start] = 0
        self.p[start] = -1
        while True:
            mincost = float('inf')
            # ??\??????????????§??????????????¨?????????????????????u???????????????
            for i in range(len(self.d)):
                if self.color[i] != Graph.Status.black and self.d[i] < mincost:  # S????±???????????????????S??¨??\?¶?????????????????????????????????????????°???????????????????
                    mincost = self.d[i]
                    u = i  # u??????????????????ID
            if mincost == float('inf'):
                break
            self.color[u] = Graph.Status.black  # ?????????u???S????±???????????????´???
            for v in range(len(self.d)):
                if self.color[v] != Graph.Status.black and self.M[u][v] != float('inf'):
                    # v????????????????????????????????°??????S???????????£???u????????????????????????????????????????????°??????????????±??§??´??°??????
                    if self.d[u] + self.M[u][v] < self.d[v]:
                        self.d[v] = self.d[u] + self.M[u][v]
                        self.p[v] = u
                        self.color[v] = Graph.Status.gray


def main(args):
    n = int(input())
    network = []
    for _ in range(n):
        network.append([int(x) for x in input().split()])

    packets = []
    p = int(input())
    for _ in range(p):
        packets.append([int(x) for x in input().split()])



    memo = [[0]*(n+1) for _ in range(n+1)]
    for i in range(1, n+1):
        g = Graph(n, network)
        g.dijkstra(i)
        for j in range(1, n+1):
            if i == j:
                continue
            if g.d[j] == float('inf'):
                memo[i][j] = float('inf')
            else:
                path = [j]
                u = j
                while g.p[u] != i:
                    path.append(g.p[u])
                    u = g.p[u]
                path.append(i)
                memo[i][j] = len(path)


    for s, d, v in packets:
        if memo[s][d] <= v:
            print(memo[s][d])
        else:
            print('NA')



if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0144

"""
import sys
from sys import stdin
input = stdin.readline
from enum import Enum


class Graph(object):
    """ single source shortest path """
    class Status(Enum):
        """ ?????????????¨??????¶??? """
        white = 1  # ????¨????
        gray = 2  # ?¨???????
        black = 3  #?¨???????

    def __init__(self, n, data):
        self.num_of_nodes = n+1
        self.color = [Graph.Status.white] * self.num_of_nodes  # ????????????????¨??????¶???
        self.M = [[float('inf')] * self.num_of_nodes for _ in range(self.num_of_nodes)]
        for i in range(self.num_of_nodes):
            self.M[i][i] = 0
        self._make_matrix(data)  # data????????????????????£??\??????(?????\?¶???¨???????????????????????§????????????)
        self.d = [float('inf')] * self.num_of_nodes  # ?§???????????????????(?????????)
        self.p = [-1] * self.num_of_nodes  # ????????????????????????????¨?????????????????????????

    def _make_matrix(self, data):
        for d in data:
            r = d[0]
            for t in d[2:]:
                self.M[r][t] = 1

    def dijkstra(self, start):
        self.d[start] = 0
        self.p[start] = -1
        while True:
            mincost = float('inf')
            # ??\??????????????§??????????????¨?????????????????????u???????????????
            for i in range(len(self.d)):
                if self.color[i] != Graph.Status.black and self.d[i] < mincost:  # S????±???????????????????S??¨??\?¶?????????????????????????????????????????°???????????????????
                    mincost = self.d[i]
                    u = i  # u??????????????????ID
            if mincost == float('inf'):
                break
            self.color[u] = Graph.Status.black  # ?????????u???S????±???????????????´???
            for v in range(len(self.d)):
                if self.color[v] != Graph.Status.black and self.M[u][v] != float('inf'):
                    # v????????????????????????????????°??????S???????????£???u????????????????????????????????????????????°??????????????±??§??´??°??????
                    if self.d[u] + self.M[u][v] < self.d[v]:
                        self.d[v] = self.d[u] + self.M[u][v]
                        self.p[v] = u
                        self.color[v] = Graph.Status.gray

    def warshallFloyd(self):
        V = self.num_of_nodes
        for k in range(V):
            for i in range(V):
                for j in range(V):
                    self.M[i][j] = min(self.M[i][j], self.M[i][k] + self.M[k][j])



def main(args):
    n = int(input())
    network = []
    for _ in range(n):
        network.append([int(x) for x in input().split()])

    packets = []
    p = int(input())
    for _ in range(p):
        packets.append([int(x) for x in input().split()])

    g = Graph(n, network)
    g.warshallFloyd()

    for s, d, v in packets:
        if g.M[s][d] < v:
            print(g.M[s][d]+1)
        else:
            print('NA')



if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0144

"""
import sys
from sys import stdin
input = stdin.readline
from enum import Enum


class Graph(object):
    """ single source shortest path """
    class Status(Enum):
        """ ?????????????¨??????¶??? """
        white = 1  # ????¨????
        gray = 2  # ?¨???????
        black = 3  #?¨???????

    def __init__(self, n, data):
        self.num_of_nodes = n+1
        self.color = [Graph.Status.white] * self.num_of_nodes  # ????????????????¨??????¶???
        self.M = [[float('inf')] * self.num_of_nodes for _ in range(self.num_of_nodes)]
        for i in range(self.num_of_nodes):
            self.M[i][i] = 0
        self._make_matrix(data)  # data????????????????????£??\??????(?????\?¶???¨???????????????????????§????????????)
        self.d = [float('inf')] * self.num_of_nodes  # ?§???????????????????(?????????)
        self.p = [-1] * self.num_of_nodes  # ????????????????????????????¨?????????????????????????

    def _make_matrix(self, data):
        for d in data:
            r = d[0]
            for t in d[2:]:
                self.M[r][t] = 1

    def dijkstra(self, start):
        self.d[start] = 0
        self.p[start] = -1
        while True:
            mincost = float('inf')
            # ??\??????????????§??????????????¨?????????????????????u???????????????
            for i in range(len(self.d)):
                if self.color[i] != Graph.Status.black and self.d[i] < mincost:  # S????±???????????????????S??¨??\?¶?????????????????????????????????????????°???????????????????
                    mincost = self.d[i]
                    u = i  # u??????????????????ID
            if mincost == float('inf'):
                break
            self.color[u] = Graph.Status.black  # ?????????u???S????±???????????????´???
            for v in range(len(self.d)):
                if self.color[v] != Graph.Status.black and self.M[u][v] != float('inf'):
                    # v????????????????????????????????°??????S???????????£???u????????????????????????????????????????????°??????????????±??§??´??°??????
                    if self.d[u] + self.M[u][v] < self.d[v]:
                        self.d[v] = self.d[u] + self.M[u][v]
                        self.p[v] = u
                        self.color[v] = Graph.Status.gray

    def warshallFloyd(self):
        for k in range(self.num_of_nodes):
            for i in range(self.num_of_nodes):
                for j in range(self.num_of_nodes):
                    if self.M[i][k] + self.M[k][j] < self.M[i][j]: 
                        self.M[i][j] = self.M[i][k] + self.M[k][j]


def main(args):
    n = int(input())
    network = []
    for _ in range(n):
        network.append([int(x) for x in input().split()])

    packets = []
    p = int(input())
    for _ in range(p):
        packets.append([int(x) for x in input().split()])

    g = Graph(n, network)
    g.warshallFloyd()

    for s, d, v in packets:
        if g.M[s][d] < v:
            print(g.M[s][d]+1)
        else:
            print('NA')



if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
class Graph():
    from collections import namedtuple
    __Pair = namedtuple("Pair", "cost point")

    def __init__(self, element_count):
        self.__element_count = element_count
        self.__adjacency_iist = [[] for _ in range(element_count)]

    def get_path(self, begin_Point, end_point, cost):
        item = self.__Pair(cost, end_point)
        self.__adjacency_iist[begin_Point].append(item)

    def dijkstra(self, begin_Point):

        from sys import maxsize as MAX_VALUE
        from queue import PriorityQueue
        state_table = {"NotVisited": 0, "Stay": 1, "Visited": 2}

        # 初期化
        pq = PriorityQueue()
        cost_table = [MAX_VALUE for _ in range(self.__element_count)]
        visit_state = [state_table["NotVisited"]
                       for _ in range(self.__element_count)]

        # 処理
        cost_table[begin_Point] = 0
        pq.put_nowait(self.__Pair(0, begin_Point))

        while not pq.empty():

            min_item = pq.get_nowait()
            min_point, min_cost = min_item.point, min_item.cost

            visit_state[min_point] = state_table["Visited"]

            if min_cost <= cost_table[min_point]:

                for cost, point in self.__adjacency_iist[min_point]:
                    if visit_state[point] != state_table["Visited"]:

                        if cost_table[min_point] + cost < cost_table[point]:
                            cost_table[point] = cost_table[min_point] + cost
                            visit_state[point] = state_table["Stay"]
                            pq.put_nowait(self.__Pair(cost_table[point], point))

        return cost_table


router_count = int(input())

graph = Graph(router_count)

for _ in range(router_count):
    data = [int(item) for item in input().split(" ")]
    data[0] -= 1

    for lp in range(data[1]):
        graph.get_path(data[0], data[2 + lp] - 1, 1)

for _ in range(int(input())):

    sender, destination, ttl = [int(item) for item in input().split(" ")]

    costs = graph.dijkstra(sender - 1)
    cost = costs[destination - 1] + 1

    if cost <= ttl:
        print(cost)
    else:
        print("NA")

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())
rlst = [None] * (n + 1)
for _ in range(n):
  lst = list(map(int, input().split()))
  r = lst[0]
  lst = lst[2:]
  rlst[r] = lst

p = int(input())

for _ in range(p):
  s, d, v = map(int, input().split())
  visited = [False] * (n + 1)
  visited[s] = True
  que = deque()
  que.append((s, 0))
  while que:
    node, dist = que.popleft()
    if node == d:
      if dist < v:
        print(dist + 1)
      else:
        print("NA")
      break
    for to in rlst[node]:
      if not visited[to]:
        que.append((to, dist + 1))
        visited[to] = True
  else:
    print("NA")

Submission status: Accepted

Solution code:
# AOJ 0144 Packet Transportation
# Python3 2018.6.23 bal4u

INF = 0x7fffffff
n = int(input())
arr = [[INF for j in range(n)] for i in range(n)]
for i in range(n):
	a = list(map(int, input().split()))
	x, k = a[0]-1, a[1]
	for j in range(k):
		y = a[j+2]-1
		arr[x][y] = 1
for k in range(n):
	arr[k][k] = 0
	for i in range(n):
		if arr[i][k] >= INF: continue
		for j in range(n):
			if arr[k][j] >= INF: continue
			arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j])
p = int(input())
for i in range(p):
	s, d, v = map(int, input().split())
	s,d = s-1, d-1
	print(arr[s][d]+1 if arr[s][d] < v else "NA")

Submission status: Accepted

Solution code:
n=input()
INF=1e100000
R=[[INF]*n for i in range(n)]
for i in range(n):
    connect=map(int,raw_input().split())
    for i in connect[2:]:
        R[connect[0]-1][i-1]=1
for k in range(n):
    for i in range(n):
        for j in range(n):
            R[i][j]=min(R[i][j],R[i][k]+R[k][j])
p=input()
for i in range(p):
    s1,d1,v1=map(int,raw_input().split())
    d=R[s1-1][d1-1]+1
    if v1>=d:
        print d
    else:
        print "NA"

Submission status: Accepted

Solution code:
from functools import lru_cache

n=int(input())
router={}
for _ in range(n):
    t=[int(i) for i in input().split(" ")]
    r=t[0]
    k=t[1]
    t=t[2::]
    router[r]=t

def transport(s,g):
    distance=[10**10 for i in range(n+1)]
    distance[s]=0
    next=[s]
    for i in range(1,n+1):
        _next=[]
        for j in next:
            _next+=router[j]
        next=list(set(_next))
        for j in next:
            distance[j]=min(i,distance[j])
    return distance[g]+1



p=int(input())
for _ in range(p):
    s,d,v=[int(i) for i in input().split(" ")]
    t=transport(s,d)
    if t<=v:
        print(t)
    else:
        print("NA")

Submission status: Accepted

Solution code:
"""
def find(s,p,g,box,cost):
    for i in rooter[p]:
        if i==g:box.append(cost+1)
        elif i==s:continue
        else:find(s,i,g,box,cost+1)
    return box
rooter={}
for i in range(int(input())):
    N=list(map(int,input().split()))
    box=[]
    for j in N[2:]:box.append(j)
    rooter[N[0]]=box

for i in range(int(input())):
    s,g,v=map(int,input().split())
    cost=1
    box=[]
    ans=min(find(s,s,g,box,cost))
    if ans<=v:print(ans)
    else:print("NA")
"""
from collections import deque

n = int(input())
rlst = [None] * (n + 1)
for _ in range(n):
    lst = list(map(int, input().split()))
    r = lst[0]
    lst = lst[2:]
    rlst[r] = lst

p = int(input())

for _ in range(p):
    s, d, v = map(int, input().split())
    visited = [False] * (n + 1)
    visited[s] = True
    que = deque()
    que.append((s, 0))
    while que:
        node, dist = que.popleft()
        if node == d:
            if dist < v:
                print(dist + 1)
            else:
                print("NA")
            break
        for to in rlst[node]:
            if not visited[to]:
                que.append((to, dist + 1))
                visited[to] = True
    else:
        print("NA")