多元宇宙稳定化

题目描述

异常现象非常危险，因为它们可以改变事件的自然进程，甚至干预关键事件，这可能会对许多宇宙造成不可逆转的后果。在斑点出现在地球-2099之后，他破坏了如此多的关键事件，以至于有 $n$ 个相邻的宇宙面临威胁：多元宇宙的网正在瓦解。你需要修复这一切！

为了稳定出现量子洞的宇宙，必须通过宇宙能量流将它们重新连接起来。已知：

1. 某些宇宙对之间由单向能量通道连接；
2. 每个宇宙恰好有两条出边；
3. 每个宇宙恰好有两条入边；
4. 每条通道由一对数 $a$ 和 $b$ 描述，表示通过该通道的能量功率必须介于 $a$ 和 $b$ 之间（包含端点）。

你需要恰好选择 $n$ 条通道，使得它们形成一个覆盖所有 $n$ 个宇宙的能量循环。换言之，这 $n$ 条通道必须构成若干个（一个或多个）环，这些环共同经过所有 $n$ 个宇宙。

此外，每条所选通道中流过的能量功率必须相同（即使通道位于不同的环上）。更形式化地说，存在一个功率值 $w$，使得对于每条被选中的通道，有 $a_i \le w \le b_i$。

请判断是否存在这样的通道集合以及功率值，使得所有条件得到满足。拯救多元宇宙！

输入格式

第一行包含一个整数 $n$ —— 宇宙的数量 ($3 \le n \le 10^5$)。

接下来的 $2n$ 行描述了所有的能量通道：首先给出从宇宙 $1$ 出发的两条通道，然后是从宇宙 $2$ 出发的两条通道，以此类推。每条通道的描述由三个整数 $t_i, a_i, b_i$ 组成 —— 目标宇宙的编号，以及通过该通道的能量功率限制 ($1 \le t_i \le n$; $1 \le a_i \le b_i \le 10^5$)。

保证每个宇宙恰好有两条入边。没有通道连接宇宙自身，但两个宇宙之间可能存在两条通道。

输出格式

如果不存在选择单一功率循环的方案，则第一行输出 -1。

否则，第一行输出所需的能量功率 $w$。第二行输出 $n$ 个空格分隔的整数 —— 所选择的通道编号（从 $1$ 到 $2n$），按照它们在输入中出现的顺序。

如果有多个正确答案，输出任意一个即可。

样例

样例输入 1

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

样例输出 1

3
1 3 5

样例输入 2

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

样例输出 2

6
1 3 5 8 10

注释

在第一个样例中，选择了编号为 $1$、$3$ 和 $5$ 的通道。第一条从宇宙 $1$ 到宇宙 $2$，限制为 $[1,3]$；第三条从宇宙 $2$ 到宇宙 $3$，限制为 $[2,4]$；第五条从宇宙 $3$ 到宇宙 $1$，限制为 $[3,5]$。得到循环 $1 \to 2 \to 3 \to 1$，经过所有宇宙，每条通道都可以通过功率 $3$ 的能量。

在第二个样例中，得到两个循环：$1 \to 2 \to 5 \to 1$ 和 $3 \to 4 \to 3$。每条所选通道都可以通过功率 $6$ 的能量。