Cho đơn đồ thị vô hướng ~G = (V,E)~ gồm ~n~ đỉnh và ~m~ cạnh vô hướng. Hãy liệt kê các đỉnh kề với từng đỉnh của đồ thị theo từng dòng.

Input:

File GRAPH.INP gồm:

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ ~(1 \le n,m \le 100)~.
• ~m~ dòng tiếp theo, mỗi dòng gồm 2 số nguyên ~u, v~ thể hiện cạnh nối giữa 2 đỉnh.

Output:

File GRAPH.OUT gồm ~n~ dòng, mỗi dòng ~i\ (i \in [1, n])~ có cấu trúc như sau:

• Số đầu tiên ghi đỉnh ~i~, các số tiếp theo là các đỉnh kề với đỉnh ~i~.
• Các số ngăn cách nhau bởi một dấu cách.

Sample Input 1

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

Sample Output 1

1 2 3
2 1 3 4 5
3 1 2 5
4 2 5
5 2 3 4

Cho đơn đồ thị vô hướng liên thông ~G = (V,E)~ gồm ~n~ đỉnh và ~m~ cạnh vô hướng. Hãy cho biết thứ tự duyệt DFS đồ thị ~G~ xuất phát từ đỉnh ~s~ (theo thứ tự từ điển nhỏ đến lớn).

Input:

File DFS.INP gồm:

• Dòng đầu tiên chứa ba số nguyên ~n~, ~m~ và ~s~ ~(1 \le n,m \le 100,\ s \in [1;n])~.
• ~m~ dòng tiếp theo, mỗi dòng gồm 2 số nguyên ~u, v~ thể hiện cạnh nối giữa 2 đỉnh ~u~ và ~v~.

Output:

File DFS.OUT gồm một dòng duy nhất là thứ tự duyệt DFS của đồ thị ~G~ xuất phát từ đỉnh ~s~. Các số ngăn cách nhau bởi một dấu cách.

Sample Input 1

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

Sample Output 1

2 1 3 5 4

Cho đơn đồ thị vô hướng liên thông ~G = (V,E)~ gồm ~n~ đỉnh và ~m~ cạnh vô hướng. Hãy cho biết thứ tự duyệt BFS đồ thị ~G~ xuất phát từ đỉnh ~s~ (theo thứ tự từ điển nhỏ đến lớn).

Input:

File BFS.INP gồm:

• Dòng đầu tiên chứa ba số nguyên ~n~, ~m~ và ~s~ ~(1 \le n,m \le 100,\ s \in [1;n])~.
• ~m~ dòng tiếp theo, mỗi dòng gồm 2 số nguyên ~u, v~ thể hiện cạnh nối giữa 2 đỉnh ~u~ và ~v~.

Output:

File BFS.OUT gồm một dòng duy nhất là thứ tự duyệt BFS của đồ thị ~G~ xuất phát từ đỉnh ~s~. Các số ngăn cách nhau bởi một dấu cách.

Sample Input 1

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

Sample Output 1

5 2 3 4 1

Cho đơn đồ thị vô hướng liên thông ~G = (V,E)~ gồm ~n~ đỉnh và ~m~ cạnh vô hướng. Hãy cho biết thứ tự vào/ra các đỉnh của hai thuật toán DFS/BFS khi bắt đầu ở đỉnh ~s~ trong đồ thị ~G~.

Input:

File DBFS.INP gồm:

• Dòng đầu tiên chứa ba số nguyên ~n~, ~m~ và ~s~ ~(1 \le n,m \le 100,\ s \in [1;n])~.
• ~m~ dòng tiếp theo, mỗi dòng gồm 2 số nguyên ~u, v~ thể hiện cạnh nối giữa 2 đỉnh ~u~ và ~v~.

Output:

File DBFS.OUT gồm 4 dòng:

• Dòng 1: Thời gian vào các đỉnh ~i\ (\forall i \in [1;n])~ theo DFS.
• Dòng 2: Thời gian ra các đỉnh ~i\ (\forall i \in [1;n])~ theo DFS.
• Dòng 3: Thời gian vào các đỉnh ~i\ (\forall i \in [1;n])~ theo BFS.
• Dòng 4: Thời gian ra các đỉnh ~i\ (\forall i \in [1;n])~ theo BFS.

Sample Input 1

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

Sample Output 1

3 2 4 1 8 9 5 
12 13 7 14 11 10 6
5 3 8 1 9 6 12 
7 4 11 2 13 10 14

Cho đơn đồ thị có hướng ~G = (V,E)~ gồm ~n~ đỉnh và ~m~ cạnh có hướng và trọng số. Hãy cho biết độ dài đường đi ngắn nhất từ đỉnh ~l~ đến đỉnh ~r~.

Đảm bảo luôn tồn tại một đường đi từ ~l~ đến ~r~.

Input:

File DIJKSTRA.INP gồm:

• Dòng đầu tiên chứa bốn số nguyên ~n~, ~m~, ~l~, ~r~ ~(3 \le n,m \le 100;\ l,r \in [1;n])~.
• ~m~ dòng tiếp theo, mỗi dòng gồm 3 số nguyên ~u, v, w~ thể hiện đường đi có hướng từ đỉnh ~u~ đến đỉnh ~v~ và có trọng số ~w~ ~(w \le 100)~.

Output:

File DIJKSTRA.OUT gồm một số nguyên là độ dài đường đi ngắn nhất từ ~l~ đến ~r~.

Sample Input 1

7 10 1 7
1 2 4
1 3 5
1 4 2
2 5 10
3 5 12
3 6 6
4 5 4
4 6 10
5 7 14
6 7 2

Sample Output 1

13

Giải thích

Đường đi ngắn nhất từ nút ~1~ đến nút ~7~ là ~1-3-6-7~, với tổng chiều dài là ~13~.