奶牛们接到了寻找一种新型挤奶机的任务，为此它们准备依次经过 颗行星，在行星上进行交易。为了方便，奶牛们已经给可能出现的 种货物进行了由 到 的标号。由于这些行星都不是十分发达。没有流通的货币，所以在每个市场里都只能用固定的一种货物去换取另一种货物。奶牛们带着一种上好的饲料从地球出发，希望在使用的物品的种类数量最少的情况下，最终得到所需要的机器。饲料的标号为 ，所需要的机器的标号为 。如果任务无法完成，输出 。
第 行是两个数字 和 。
第 到 行，每行是两个数字 和 ，表示第 颗行星为得到 愿意提供 。
输出最少经手物品数。
6 5 1 3 3 2 2 3 3 1 2 5 5 4
4
奶牛们至少需要 种不同标号的物品，先用 去交换 ，再用 去交换 ，最后用 交换得到 。
，。
