/* ????????????????????????????????????????????? */
#include <stdio.h>

/* ?????°???????????? */
typedef	void			VD;
typedef	signed char		I1;
typedef unsigned char 	U1;
typedef	signed short	I2;
typedef unsigned short 	U2;
typedef	signed int		I4;
typedef unsigned int 	U4;

/* ?????°?????? */
#define MAX_ROUTER 100
#define MAX_TTL 10000

#define CONNECT 1
#define DISCONNECT 0
#define SENTINEL -1

#define TRUE 1
#define FALSE 0

#define INPUT_SUCCESS 0
#define INPUT_ERORR -1

/* ????????????????????£?¨? */
VD setInit(VD);
I1 inputConnectInfo(VD);
I1 inputTransmitPacket(VD);
I4 CalcDijikstra(I4 i4Sender,I4 i4Destination,I4 i4TTL);
/* ??°?????????????????° */
I1 u1Connect[MAX_ROUTER+1][MAX_ROUTER+1];
I4 i4RouterNum;

I4 main(VD)
{
	I1 i1ErrorCheck;
	I4 i4CalcNum;
	I4 i4RoopCnt1;
	I4 i4RoopCnt2;
	
	setInit();
	i1ErrorCheck = inputConnectInfo();
	if(i1ErrorCheck == INPUT_SUCCESS){
		scanf("%d",&i4CalcNum);
		for( i4RoopCnt1=0; i4RoopCnt1<i4CalcNum; i4RoopCnt1++)
		{
			inputTransmitPacket();
		}
	}
	else{
		;
	}
	return 0;
}

VD setInit(VD)
{
	I4 i4RoopCnt1;
	I4 i4RoopCnt2;
	
	for( i4RoopCnt1=1; i4RoopCnt1<=MAX_ROUTER; i4RoopCnt1++)
	{
		for(i4RoopCnt2=1; i4RoopCnt2<=MAX_ROUTER; i4RoopCnt2++)
		{
			u1Connect[i4RoopCnt1][i4RoopCnt2] = DISCONNECT;
		}
	}
	return;
}

I1 inputConnectInfo(VD)
{
	I1 i1Return;
	I4 i4RoopCnt1;
	I4 i4RoopCnt2;
	I4 i4RouterCnt;
	I4 i4ConnectNum;
	I4 i4AccessPoint;
	
	i1Return = INPUT_SUCCESS;
	
	scanf("%d",&i4RouterNum);
	if(i4RouterNum <= (I4)MAX_ROUTER){
		for( i4RoopCnt1=1; i4RoopCnt1<=i4RouterNum; i4RoopCnt1++)		{
			scanf("%d%d",&i4RouterCnt,&i4ConnectNum);
			for( i4RoopCnt2=0; i4RoopCnt2<i4ConnectNum; i4RoopCnt2++)			{
				scanf("%d",&i4AccessPoint);
				u1Connect[i4RouterCnt][i4AccessPoint] = CONNECT;
			}
			u1Connect[i4RouterCnt][i4RouterNum+1] = SENTINEL;
		}
	}
	else{
		i1Return = INPUT_ERORR;
	}
	return i1Return;
}

I1 inputTransmitPacket(VD)
{
	I1 i1Return;
	I4 i4StartRouter;
	I4 i4GoalRouter;
	I4 i4TTL;
	I4 i4Ans;
	
	i1Return = INPUT_SUCCESS;
	
	scanf("%d%d%d",&i4StartRouter,&i4GoalRouter,&i4TTL);
	if(i4TTL <= MAX_TTL){
		i4Ans = CalcDijikstra(i4StartRouter,i4GoalRouter,i4TTL);
		if(i4Ans > 0){
			printf("%d\n",i4Ans);
		}
		else{
			printf("NA\n");
		}
	}
	else{
		i1Return = INPUT_ERORR;
	}
	return i1Return;
}

I4 CalcDijikstra(I4 i4Sender,I4 i4Destination,I4 i4TTL)
{
	I1 i1StarTable[MAX_ROUTER+1][MAX_ROUTER+1];
	I4 i4MinVal[MAX_ROUTER+1];
	I4 i4RoopCnt1;
	I4 i4RoopCnt2;
	I4 i4RoopCnt3;
	
	for( i4RoopCnt1=1; i4RoopCnt1<=MAX_ROUTER; i4RoopCnt1++){
		i4MinVal[i4RoopCnt1] = 0;
		for(i4RoopCnt2=1; i4RoopCnt2<=MAX_ROUTER; i4RoopCnt2++){
			i1StarTable[i4RoopCnt1][i4RoopCnt2] = FALSE;
		}
	}
	
	i1StarTable[1][i4Sender] = TRUE;
	
	for(i4RoopCnt1=1; i4RoopCnt1<MAX_ROUTER; i4RoopCnt1++){
		if(i4TTL <= i4RoopCnt1){
			return 0;
		}
		else{
			;
		}
		for(i4RoopCnt2=1; i4RoopCnt2<=MAX_ROUTER; i4RoopCnt2++){
			if(i1StarTable[i4RoopCnt1][i4RoopCnt2] == TRUE){
				for(i4RoopCnt3=1; i4RoopCnt3<=MAX_ROUTER; i4RoopCnt3++){
					if(u1Connect[i4RoopCnt2][i4RoopCnt3] == CONNECT){
						if(i4RoopCnt3 == i4Destination){
							return i4RoopCnt1+1;
						}
						else{
							;
						}
						i1StarTable[i4RoopCnt1+1][i4RoopCnt3] = TRUE;
					}
					
				}
			}
			else{
				;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 2664