Migrated from Lutece 1148 秋实大哥与时空漫游

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

秋实大哥通过全国的连锁快餐店发家致富，赚了大钱，接下来他打算通过这些钱实现他的另一个梦想————遨游太空，漫游星际。

秋实大哥满怀期待的出发了。

.......啦啦啦啦啦啦啦啦啦......

最后，秋实大哥花完了钱，觉得是时候回地球继续赚钱和过节了。

但是却被告知回地球的专机只有一架————在$Tp$星球且在$Tt$时刻起飞（因此必须要在$Tt$时刻之前到达该$Tp$星球），而秋实大哥现在所处的时空是$Sp$星球上的$St$时刻。为了能赶上那班回地球的专机，秋实大哥可以使用一系列的时空传送门。

（时空传送门是发达星球的日常交通产物，而像地球这样的发展中星球只有最原始的宇宙飞船。）

每个传送门有4个属性，起点星球$a$，终点星球$b$，起点时刻$c$，终点时刻$d$。如果秋实大哥想使用某时空传送门，那么他就必须在$c$时刻之前到达星球$a$，然后等到$c$时刻他就可以通过该传送门到达$d$时刻的星球$b$。

在任意时刻，如果在同一星球上有两个秋实大哥，就会引发“祖父悖论”！

这就犯了时空漫游的大忌，时空就会扭曲，宇宙就会产生巨大的黑洞甚至引发降维，世界就会毁灭！

得知稍有不当就会毁灭世界，秋实大哥现在很慌，不知道到底怎么走才能赶上回地球的末班车。

但是迫不及待想见到秋实大哥的你马上给出了正确答案。

Input

第一行一个整数$N$,$M$，分别表示星球的个数和传送门的个数

接下来$M$行，表示每个传送门的四个属性$a_i$,$b_i$,$c_i$,$d_i$。

最后一行四个整数$Sp$,$Tp$,$St$,$Tt$分别表示秋实大哥所处的初始时刻和星球，以及末班车的地点和时间。

$1\leq Sp,Tp,ai,bi\leq N$

$0\leq St,Tt,ci,di\leq 10^7$

$N\leq 10^5,M\leq 5×10^5$

Output

如果秋实大哥无论如何都不能赶上，输出-1。

否则：

第一行一个整数$k$，表示秋实大哥所要经历的传送门个数。

第二行$k$个整数，按顺序输出秋实大哥使用传送门编号（从1开始编号）。

任意的合法解都是支持的。

Samples

3 3
1 2 4 2
2 1 2 1
1 1 1 0
1 1 3 0

3
1 2 3

3 3
1 2 4 2
2 1 2 1
1 1 1 0
1 2 0 1

-1

Resources

2015 UESTC Training for Graph Theory