Cho một đồ thị có hướng gồm ~ n ~ đỉnh, được đánh số từ 1 đến ~ n ~. Mỗi đỉnh có thể có nhiều cung đi đến các đỉnh khác (không có cung tự nối).

Bạn được cung cấp hai đỉnh:

• ~ s ~: đỉnh xuất phát
• ~ t ~: đỉnh đích

Yêu cầu:

1. Tìm tất cả các đỉnh mà ta có thể đi từ ~ s ~ đến được, theo thứ tự duyệt DFS.
2. Nếu tồn tại đường đi từ ~ s ~ đến ~ t ~, hãy in ra một đường đi bất kỳ từ ~ s ~ đến ~ t ~. Ngược lại, in ra -1.

Input

Gồm ~ n + 1 ~ dòng:

• Dòng đầu tiên chứa ba số nguyên:
  ~ n ~, ~ s ~, ~ t ~ — số đỉnh, đỉnh bắt đầu và đỉnh đích.
  (1 ≤ ~ n ~ ≤ 100000, 1 ≤ ~ s, t ~ ≤ ~ n ~)

• Dòng thứ ~ i+1 ~ (với ~ 1 \le i \le n ~) chứa danh sách các đỉnh mà từ đỉnh ~ i ~ có cung đi tới, kết thúc bằng số 0.

Output

• Dòng đầu tiên: In ra các đỉnh có thể đến được từ ~ s ~, theo thứ tự duyệt DFS (không đệ quy), cách nhau bởi dấu cách.
• Dòng thứ hai:
  • Nếu tồn tại đường đi từ ~ s ~ đến ~ t ~, in ra một đường đi bất kỳ (các đỉnh cách nhau bởi dấu cách).
  • Nếu không tồn tại đường đi, in ra -1.

Ví dụ

Input

8 1 5
2 3 0
3 4 0
1 5 0
6 0
0
2 0
8 0
0

Output

1 2 3 5 4 6
1 2 3 5

Giải thích

• Từ đỉnh 1 có thể đến các đỉnh: 2 → 3 → 5 → 4 → 6 (theo DFS).
• Đường đi từ 1 đến 5 có thể là: 1 → 2 → 3 → 5.

Chấm điểm

Bài gồm 2 subtask:

Chương trình cần chạy đúng và trong giới hạn thời gian với mọi subtask để đạt điểm tối đa.

Lưu ý

• Dữ liệu đảm bảo không có cung tự nối (self-loop).
• Có thể có nhiều cung từ một đỉnh đến các đỉnh khác.
• Không yêu cầu đường đi ngắn nhất, chỉ cần một đường đi bất kỳ từ ~ s ~ đến ~ t ~ là được.

Một đồ thị vô hướng gồm ~ n ~ đỉnh và ~ m ~ cạnh được biểu diễn bằng danh sách kề.

Hai đỉnh được gọi là thuộc cùng một thành phần liên thông nếu tồn tại đường đi giữa chúng thông qua các cạnh của đồ thị.

Hãy:

1. Đếm số lượng thành phần liên thông của đồ thị.
2. In ra danh sách các đỉnh thuộc từng thành phần liên thông (mỗi thành phần là một dòng, các đỉnh được in theo thứ tự từ bé đến lớn).

Input

• Dòng đầu tiên chứa hai số nguyên ~ n ~, ~ m ~ — số đỉnh và số cạnh.
  (1 ≤ ~ n ~ ≤ 100000, 0 ≤ ~ m ~ ≤ 200000)

• Tiếp theo là ~ m ~ dòng, mỗi dòng chứa hai số nguyên ~ u, v ~ — biểu diễn một cạnh nối giữa đỉnh ~ u ~ và đỉnh ~ v ~.
  (1 ≤ ~ u, v ~ ≤ ~ n ~, ~ u \ne v ~)

Output

• Dòng đầu tiên: In ra số lượng thành phần liên thông của đồ thị.
• Mỗi dòng tiếp theo: In ra danh sách các đỉnh thuộc một thành phần liên thông, theo thứ tự từ bé đến lớn, các đỉnh cách nhau bởi dấu cách.

Ví dụ

Input

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

Output

3
1 2 3
4 5
6 7 8

Giải thích

• Có 3 thành phần liên thông:
  • {1, 2, 3}
  • {4, 5}
  • {6, 7, 8}

Chấm điểm

Chương trình cần chạy đúng và trong giới hạn thời gian với mọi subtask để đạt điểm tối đa.

Lưu ý

• Bạn cần sử dụng DFS để duyệt đồ thị.
• Có thể sử dụng danh sách kề để lưu đồ thị.