Bob is a successful entrepreneur. He is working on a very important project and needs to make some decisions. Therefore, he drew a graph where nodes represent activities. A directed edge is drawn between two nodes if and only if the accomplishment of an activity depends on the completion of the other one. Weights are the costs of transiting from one activity to another; if negative, it means Bob earns more than he spends. His graph looks like this:
Help Bob calculate the most profitable sequence of activities in order to perform activity . In other words, write the space-separated ordered array of nodes in the shortest path from node to node .
Answer format example: 1 2 3 4 5 6