题目描述:
编程实现:
在一个神奇空间里有N个房间,房间从1到N编号,每个房间可能有一个或多个传送门,每个传送门都有一个编号,如果相同编号的传送门同时出现在多个房间中,表示这些房间可以互通。
给定两个房间的编号A和B,请找出从房间A到达房间B最少需要经过几个传送门。
例如:N=3,3个房间中传送门的编号分别为:
房间1:1、4、6;
房间2:2、3、4,8;
房间3:3、6、9。
其中房间1和房间2互通,共用4号传送门;房间1和房间3互通,共用6号传送门;房间2和房间3互通,共用3号传送门;
当A=1,B=2,从房间1到达房间2,共有两种路线:
路线1:从房间1通过4号传送门进入房间2,共经过1个传送门;
路线2:从房间1通过6号传送门进入房间3,再从房间3通过3号传送门进入房间2,共经过2个传送门;
故从房间1到达房间2最少需要经过1个传送门。
输入描述
第一行输入一个正整数N(2≤N≤20),表示房间数量。
接下来输入N行,每行包含多个正整数(1≤正整数≤100),第2行到第N+1行依次表示1到N号房间内所有传送门的编号,正整数之间以一个英文逗号隔开。
最后一行输入两个正整数A和B(1≤A≤N,1≤B≤N,且A≠B),表示两个房间的编号,正整数之间以一个英文逗号隔开。
输出描述
输出一个整数,表示从房间A到达房间B最少需要经过几个传送门,如果房间A不能到达房间B,则输出-1。
样例输入
3
1,4,6
2,3,4,8
3,6,9
1,2
样例输出
1