时间限制：1秒　　内存限制：256M

---

【题目描述】

　　A国有 \(n\) 座城市，编号从 1 到 \(n\)，城市间有 \(m\) 条双向道路，车辆在每一条道路上的行使时间为 \(T\)。

　　有一辆货车从城市 1 到城市 \(n\)，同时有一辆超重检查车从城市 \(n\) 到城市 1。在途中遇到检查车显然是货车司机不愿意看见的。

　　货车和检查车不会在检查站停留，他们可以在一条路上往不同方向走，但任何时刻双方都不能在城市中相遇。

　　现在请你计算，最早什么时刻，货车和检查车能同时到达各自的目的地。

【输入格式】

　　第一行包含 3 个整数，\(n,m,T\)，表示有 \(n\) 座城市和 \(m\) 条双向道路，以及每条道路的行驶时间。
　　接下来 \(m\) 行，每行包含两个整数 \(x,y\)，表示编号为 \(x\) 的城市与编号为 \(y\) 的城市间有一条双向道路。

【输出格式】

　　一个整数，表示货车和检查车同时到达目的地的最早时刻。若无解则输出 -1。

【输入输出样例1】

　Input

2 1 1
1 2

　Output

1

【输入输出样例2】

　Input

7 6 2
1 2
2 7
7 6
2 3
3 4
1 5

　Output

12

【输入输出样例2说明】

　　货车沿着1-2-3-4-3-2-7的路线走，检查车沿着7-6-7-2-1-5-1的路线走。

【输入输出样例3】

　Input

7 5 2
1 2
2 7
7 6
2 3
3 4

　Output

-1

【数据限制】

　　对于 \(40\%\) 的数据，\(1≤n≤100\)。
　　对于 \(100\%\) 的数据，\(1≤n≤500\)，\(1≤m≤10000\)，\(0<T<1000\)。

【来源】

　　Mr.he