Pemguimn nhặt được mảnh giấy ghi các dòng code của một chương trình như sau:

void dfs(int i, int pre){
    time_in[i] = ++timedfs;
    for(int x : adj[i]){
        if(x == pre) continue;
        dfs(x, i);
    }
    time_out[i] = timedfs;
}

void main(){
    // dựng cây
    dfs(1, -1);
}

• Được biết, đoạn code trên là mã của một thuật toán nổi tiếng, đường đi Euler trên cây. Ngoài ra, khi tìm được các cạnh của cây thì Pemguimn sẽ biết được mật mã dẫn đến thế giới Anime.

• Tuy nhiên, cây đã bị giấu mất, và Pemguimn chỉ biết được giá trị của mảng timein[] và timeout[] cũng như giá trị ~n~, số đỉnh của cây. Các bạn hãy giúp Pemguimn mở được cánh cổng tới thế giới của harem nhé!

• Ngoài ra, tồn tại trường hợp ai đó đã chơi khăm Pemguimn và thay đổi giá trị của mảng timein[] hoặc timeout[] nên không tồn tại cây thỏa giá trị của hai mảng trên. Trong trường hợp đó, hãy in ra ~-1~ trên một dòng duy nhất.

Yêu cầu

Cho giá trị ~n~, số đỉnh của cây , và giá trị của các mảng timein[], timeout[] của từng đỉnh được mô tả như trên.

Với mỗi đỉnh ~i~, bạn hãy in ra số đỉnh kể với đỉnh ~i~ trong cây và in ra số hiệu của các đỉnh đấy.

Input

• Dòng đầu chứa ~n~, số đỉnh của cây, ~n~ (~1 \leq n \leq 5 \cdot 10^5~).

• Dòng thứ ~i~ trong ~n~ dòng tiếp theo, mỗi dòng chứa hai giá trị timein[i] và timeout[i], (~1 \leq~ timein[i], timeout[i] ~\leq n~), lần lượt là giá trị của giá trị timein và timeout của đỉnh thứ ~i~.

Output

Trong trường hợp tồn tại đáp án:

• In đáp án trên ~2 \times n~ dòng:

  • Dòng thứ ~2 \times i - 1~ in ra ~m~, số đỉnh kề với đỉnh ~i~ trong cây.

  • Dòng thứ ~2 \times i~ in ra ~m~ số, số hiệu của các đỉnh kề với ~i~ được liệt kê theo thứ tự tăng dần, cách nhau bởi dấu cách.

Trong trường hợp không tồn tại cây thỏa đề bài thì in ra ~-1~ trên một dòng duy nhất.

Scoring

• Subtask 1 (~25\%~): ~n \leq 10~.

• Subtask 2 (~25\%~): ~n \leq 100~.

• Subtask 3 (~50\%~): Không có ràng buộc gì thêm.

Sample Input 1

4
1 4
2 4
3 3
4 4

Sample Output 1

1
2 
3
1 3 4 
1
2 
1
2

Notes

• Trong test ví dụ trên, đỉnh ~1~ kề với ~1~ đỉnh duy nhất trong cây, là đỉnh ~2~.

• Tương tự, đỉnh ~2~ kề với ~3~ đỉnh là ~1, 3~ và ~4~.

• Đỉnh ~3~ và ~4~ chỉ kề với một đỉnh duy nhất là đỉnh ~2~.