Break the loop and leave the list

Medium

2000 ms limit256 MB memoryTwo pointers Linked lists

Stuck?

Show a hint

Find where the loop begins, then walk round to the node whose next points at it. That one link is the only thing to change.

The idea behind this problem

Loops in a linked list: two walkers, no extra memory

Next in this lesson

Find the middle in one pass

A linked list may point back at one of its own nodes. Break that link so the list ends properly, keeping every node and their order, and return the head.

If there is no loop, return the list unchanged.

Worked example#

1 -> 2 -> 3 -> 4 -> 5
          ^         |
          +---------+

The 5 points back at the 3. Set the 5's next to nothing and the list becomes 1 2 3 4 5, which ends.

The idea#

You already know how to find where a loop begins. This is one step further: the node to change is the one just before that, the last node of the loop, and its next is what points backwards.

Two ways to reach it, both fine:

Find the start, then walk to the node before it. Once you know the start, walk round the loop until the node whose next is the start. Clear that next.

Advance two walkers and watch for the node. Put one walker at the head and one at the meeting point, then step them together as usual, but keep hold of the second walker's previous node. When they meet, that previous node is the one to cut.

Nothing is deleted and nothing is reordered. Only one link changes.

Why the answer is always just the values#

Removing a loop never adds, drops or moves a node, so a correct answer prints the values in the order they were given. That is what makes this a good check: a solution that leaves the loop in has nothing sensible to print at all.

Constraints#

0 <= n <= 100000

About the input#

The list is written as a count, then the values, then one more number saying which position the last node points back to. -1 means the list simply ends.

Input

head is a count, then that many values, then the position the tail links back to, or -1.

Output

A count is not printed. Print the values of the list, separated by spaces.

Examples

Input

5
1 2 3 4 5
2

Output

1 2 3 4 5

The link from 5 back to 3 is cut, and the list ends.

Input

4
7 8 9 10
0

Output

7 8 9 10

The whole list was the loop, and it now ends after 10.

Input

3
1 2 3
-1

Output

1 2 3

No loop, so nothing changes.

Something wrong with this problem? Report an issue

Ready to try it

Write your solution in C, C++, Java or Python and see every test case come back with the time and memory it took.

Create a free account Sign in

Free, and it stays free. No card.