Depth First Search (DFS) Graph Traversal

Problem Statement:

You are given a graph with \(N\) nodes represented by an adjacency list, along with a starting node \(s\). Your task is to perform a Depth First Search (DFS) starting from node \(s\) and output the nodes in the order they are visited. The DFS should only traverse the connected component that contains the starting node.

The DFS procedure is defined recursively. At each node, visit it and then recursively visit each of its unvisited neighbors in the order provided. Use the standard recursive approach for DFS traversal.

Input and Output Format: The graph is given via standard input and the traversal order is expected on standard output. Detailed descriptions are provided below.

Note: If the graph is disconnected, only the nodes reachable from the starting node \(s\) are output.

inputFormat

Input Format:

• The first line contains an integer \(N\) representing the number of nodes in the graph.
• The following \(N\) lines describe the adjacency list for each node. Each line starts with an integer \(k\) (the number of neighbors), followed by \(k\) space-separated integers denoting the neighbors of that node.
• The last line contains an integer \(s\) representing the starting node for DFS.

You should read the input from standard input (stdin).

outputFormat

Output Format:

Output a single line containing the DFS traversal order (i.e., the list of nodes visited) as space-separated integers. The output should be written to standard output (stdout).

## sample

4
2 1 2
2 0 3
1 0
1 1
0

0 1 3 2