#ABC485E. 彩色路径
彩色路径
彩色路径
题目描述
有 个城市和 条单向道路。第 条道路从城市 通向城市 ,颜色为 。
你希望从城市 出发,反复经过道路到达城市 。但是,不能连续两次经过颜色相同的道路。
请判断能否从城市 到达城市 ;如果可以,求出最少需要经过多少条道路。
输入格式
输入第一行为两个整数 。
接下来 行,第 行为三个整数 。
输出格式
如果无法从城市 到达城市 ,输出 ;否则输出最少需要经过的道路条数。
6 10
1 2 1
2 4 2
2 5 2
3 6 5
4 3 3
5 2 3
5 3 2
5 6 2
6 1 3
6 5 3
4
样例 1 解释
依次经过第 条道路即可从城市 到达城市 ,颜色依次为 ,没有连续相同的颜色,共经过 条道路。
3 5
1 2 1
1 2 1
1 2 2
1 2 2
1 2 3
-1
8 10
1 2 1
2 3 2
2 4 1
3 2 3
4 5 2
4 6 1
5 4 3
6 7 2
6 8 1
7 6 3
10
数据范围
对于所有测试数据,保证:
- ;
- ;
- ,;
- ;
- 所有输入值均为整数。
子任务
本题共 20 个测试点,按测试点计分:
| 测试点 | 分值 | 每个测试点 | 特殊性质 |
|---|---|---|---|
| 无特殊限制 |
每个测试点单独评分,全部测试点的得分之和即为本题得分。
相关
在下列比赛中: