Description

悠悠岁月,不知不觉,距那传说中的pppfish晋级泡泡帝已是过 去数十年。数十年 中,这颗泡泡树上,也是再度变得精彩,各种泡泡 天才辈出,惊艳世人,然而,似乎 不论后人如何的出彩,在他们的头 顶之上,依然是有着一道身影而立。 泡泡帝,pppfish。 现在,pppfish即将带着被自己收服的无数个泡泡怪前往下一个 空间,而在前往下 一个空间的道路上,有N个中转站,和M条空间虫洞连接中转站(双向通道,可有重 边,可有环),然而,通过虫洞 是要一定的条件的,pppfish将手下所有泡泡怪编号为 1,2 … +∞,对于每个空间虫洞,有两个值L和R,表示此虫洞只允许编号从L到 R的泡 泡怪通过,pppfish现在在1号中转站,他想带尽可能多的泡 泡怪到达N号中转站,于是 pppfish找到了机智的你,希望你告诉他最多可以带多少个泡泡怪,同时他还想知道所有泡泡怪的编号(若有多组解取字典序最小的一组 )

Input

第一行两个用空格隔开的整数N,M(2<=N<=1000,0<=M<=3000) 接下来M行,每行四个用空格隔开的整数a,b,l,r 表示在a,b中转站间有一个空间虫洞允许编号l~r的泡泡怪通过。(1<=a, b<=N,1<=l<=r<=1e6)

Output

第一行一个整数ans,表示最多能携带的泡泡怪数量 接下来一行ans个用空格隔开的正整数,表示泡泡怪的编号,从小到大依次输出,如 果没有泡泡怪能通过只要输出“0”就可以了

Sample Input 1
4 4
1 2 1 10
2 4 3 5
1 3 1 5
2 4 2 7
Sample Output 1
6
2 3 4 5 6 7
Sample Input 2
2 2
1 2 1 3
1 2 4 6
Sample Output 2
3
1 2 3
Hint

【数据范围】

30%的数据 1 <= N, M <= 10

100%的数据 2 <= N <= 1000, 0 <= M <= 3000, 1 <= a, b <= N, 1 <= l <= r <= 106