using System;
using System.Collections.Generic;
using System.Linq;

public class Node
{
	public bool UsedOnce;
    public int Id;
    public bool Visited;
    public Node[] Children;
    
    public Node(int id, Node[] children)
    {
    	UsedOnce = false;
    	Visited = false;
    	Id = id;
    	Children = children;
    }
    
    public Node(int id)
    {
    	UsedOnce = false;
    	Visited = false;
    	Id = id;
    	Children = new Node[0];
    }
}

public class Test
{
	public static void DFS(Node node)
	{
	    if (node.Children.Length == 0) // if it is a leaf (no children) - output
	    {
	    	OutputAndMarkAsUsed();
	    	return;
	    }
	
	    foreach (var child in node.Children)
	    {
	        if (!child.Visited) // for every not visited children call DFS
	        {
	            child.Visited = true;
	            currentPath.Add(child);
	            DFS(child); 
	            currentPath.Remove(child);
	            child.Visited = false;
	        }
	    }
	}
	
	private static void OutputAndMarkAsUsed()
	{
		int startId = 0;
    	for (int i = 0; i < currentPath.Count - 1; i++)
    		if (currentPath[i + 1].UsedOnce == false) 
    		{
    			startId = i;
    			break;
    		}
    	
    	for (int i = startId; i < currentPath.Count; i++)
    	{
    		Console.Write("{0} ", currentPath[i].Id);
    		currentPath[i].UsedOnce = true;
    	}
        
        Console.WriteLine();
        
        return;
	}
	
	private static List<Node> currentPath = new List<Node>();
	
	public static void Main()
	{
		var root = new Node(1, new [] {
			new Node(2, new [] {
				new Node(5),
				new Node(6)
			}),
			new Node(3, new [] {
				new Node(7)
			}),
			new Node(4, new [] {
				new Node(8),
				new Node(9)
			})
		});
		
		root.Visited = true;
        currentPath.Add(root);
        DFS(root); 
	}
}