题目描述

Kyusho 为了研究竞争对手，决定乘坐保加利亚铁路出行。共有 $N$ 个车站，编号为 $1$ 到 $N$；另有 $M$ 条双向铁路，按输入顺序编号为 $1$ 到 $M$。

两座车站之间可能有多条铁路。保证从任意车站都可以通过铁路到达任意其他车站。

Kyusho 希望：

• 每条铁路至少经过一次；
• 每条铁路至多经过两次；
• 其中某些“更特殊”的铁路必须恰好经过一次。

他要求整条路线从车站 $1$ 出发，并最终回到车站 $1$。

具体地，每条铁路用三个整数 $u,v,t$ 描述：

• 表示它连接车站 $u$ 和 $v$；
• 若 $t=2$，则这条铁路最多可以经过两次；
• 若 $t=1$，则这条铁路必须恰好经过一次。

请帮助 Kyusho 构造一条满足条件的路线。

注意：对于允许经过两次的铁路，并不是必须经过两次，只要求至少一次，至多两次。

输入格式

第一行输入两个正整数 $N,M$，表示车站数和铁路数。

接下来 $M$ 行，每行三个正整数 $u,v,t$，表示一条铁路。

输出格式

若存在满足条件的路线：

• 第一行输出一个整数 $S$，表示所选路线经过的铁路总次数；
• 第二行输出 $S$ 个介于 $1$ 到 $M$ 之间的整数，表示按经过顺序给出的铁路编号。

如果有多种可行解，输出任意一种即可。

如果不存在满足条件的路线，输出一行 -1。

特别地：若你仅正确输出了“答案形式”（即 -1 或某个自然数；若存在路线，最简单可以只输出 1），则该测试点可获得该测试点 25% 的分数。

数据范围

• $2\le N\le 10^5$
• $1\le M\le 10^6$
• $1\le u,v\le N$
• $u\ne v$

子任务

只有当某个子任务的所有测试全部通过时，才能获得该子任务的分数。

样例 #1

输入 #1

10 18
1 10 2
7 9 2
2 6 1
3 7 1
3 8 1
9 2 2
2 8 2
4 2 1
4 6 2
6 8 2
3 6 2
1 9 1
4 9 1
10 7 2
7 5 2
5 3 2
4 7 1
10 5 1

输出 #1

22
1 14 2 6 3 9 8 7 5 4 15 16 11 10 10 11 16 18 14 17 13 12

说明 #1

• 绿色边表示可以经过两次的铁路；
• 黑色边表示必须恰好经过一次的铁路。

样例 #2

输入 #2

6 9
1 3 2
1 4 1
3 4 1
2 4 2
2 3 1
3 5 2
5 6 1
2 6 1
4 6 1

输出 #2

-1

说明 #2

该样例不存在符合要求的路线。