import java.lang.*;
import java.util.*;
import node.*;

class CloneGraph {
	public static GraphNode cloneGraph(GraphNode node) {
		Stack<GraphNode> stack = new Stack<GraphNode>();
		ArrayList<GraphNode> visited = new ArrayList<GraphNode>();
		stack.push(node);
		GraphNode clone = new GraphNode(node.val, node.neighbors);
		while (!stack.empty()) {
			node = stack.pop();
			if (visited.contains(node))
				continue;
			GraphNode curr = new GraphNode(node.val, node.neighbors);
			visited.add(node);
			System.out.println("Node: " + node.val);
			System.out.print("Neighbors: ");
			for (GraphNode neighbor : node.neighbors) {
				stack.push(neighbor);
				System.out.print(neighbor.val + " ");
			}
			System.out.println();
		}
		return clone;
	}

	public static void main(String[] args) {
		GraphNode head = new GraphNode(1);
		GraphNode first = new GraphNode(2);
		GraphNode second = new GraphNode(3);
		GraphNode third = new GraphNode(4, new ArrayList<>(Arrays.asList(first, second)));
		second.neighbors = new ArrayList<>(Arrays.asList(head, third));
		first.neighbors = new ArrayList<>(Arrays.asList(head, second));
		head.neighbors = new ArrayList<>(Arrays.asList(first, second));

		GraphNode curr = cloneGraph(head);
	}
}