阳阳是一个任务狂人，他最喜欢看到游戏的任务列表中，「可以开始」一栏为空。这天他又发现了一款新游戏……
这个游戏由 个城市构成，用 到 的整数编号。其中城市 有 个任务需要全部完成。但是，每次到达一个城市必须且只能完成一个任务。如果一个城市没有可以做的任务，阳阳就不能到达这个城市。做完任务以后，必须通过通道或者传送卷轴到达另外一个城市。
通道总共有 条，它们单向连接两个城市。通道 表示从城市u到城市v的通道。奇怪的是，通道 只允许玩家至多通过 次。更奇怪的是，对于任意的通道 和通道 ，若 ，则 。
传送卷轴可以从任意一个城市到达任意一个城市。特别地，可以回到原来的城市，算又到达这个城市一次，这时可以且必须再做一个任务。另外，最初你需要使用一个卷轴到达任意一个城市，最终可以停留在任意一个城市。
阳阳想知道，完成所有的任务最少需要使用多少次转送卷轴。
