Trong thư mục root có chứa tổng cộng \(n\) thư mục và tập tin (bao gồm chính nó). Dễ thấy, ngoại trừ thư mục root thì mỗi tập tin hoặc thư mục đều có chính xác một thư mục bao chứa nó - tạm gọi là thư mục cha. Vì thế có tổng cộng \(n-1\) quan hệ cha-con trong thư mục root. Bạn được cho biết tên của các thư mục và tập tin, cũng như các quan hệ cha-con. Nhằm theo dõi nội dung của thư mục, bạn cần in ra tất cả mọi đường dẫn hợp lệ, (bắt đầu bằng root). Hãy lập trình giải quyết vấn đề trên.

Input

• Dòng đầu chứa \(n\) : số lượng tập tin và thư mục.

• Dòng tiếp theo chứa \(n\) xâu là tên của tập tin hoặc thư mục tương ứng.

• \(n-1\) dòng tiếp theo, mỗi dòng chứa 2 số \(u,v\), có ý nghĩa là tên thứ \(u\) trong danh sách tên trên bao chứa tên thứ \(v\). Dữ liệu đảm bảo \(u\) là một thư mục.

Dữ liệu đảm bảo tồn tại duy nhất một xâu root.

Output

• In ra \(n\) dòng, dòng thứ \(i\) là đường dẫn tới tập tin hoặc thư mục thứ \(i\).

Constraints

• \(1 \le n \le 200\) trong mọi test

Example

8
break.zip program.docx sense.exe list.mp3 outside.pptx root purpose.jpg okay.pptx 
6 7
6 2
6 4
6 8
6 5
6 1
6 3

root/break.zip
root/program.docx
root/sense.exe
root/list.mp3
root/outside.pptx
root
root/purpose.jpg
root/okay.pptx