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